CodeOn Cooperative Popular Content Distribution for Vehicular Networks using Symbol Level Network Coding.

A Reference Programming Model for Building Context%2DAware Application.

Constraint%2DAware Complex Event Pattern Detection over Streams.

Time Delay Signal Process Assisted by Virtual Instrument.

Performance Enhancement for Unlicensed Users in Coordinated Cognitive Radio Networks via Channel Reservation.

The calculation and analysis of Water Resource Carrying Capacity in Chongqing

A Study of Nonlinear Time%2DVarying Spectral Analysis Based on HHT

Application of neural network technique for logging fluid identification in low resistance reservoir.

Robust ECG Biometrics by Fusing Temporal and Cepstral Information.

Cardiac interventions under MRI guidance using robotic assistance.

Group Device Pairing based Secure Sensor Association and Key Management for Body Area Networks.

A modular security architecture for managing security associations in MANETs.

Towards Automated Structure%2DBased NMR Resonance Assignment.

Optimal Joint Power and Transmission Time Allocation in Cognitive Radio Networks.

Information Distance
While Kolmogorov complexity is the accepted absolute measure of information  content in an individual finite object, a similarly absolute notion  is needed for the information distance between two individual objects, for  example, two pictures. We give several natural definitions of a universal  information metric, based on length of shortest programs for either ordinary  computations or reversible (dissipationless) computations. It turns  out that these definitions are equivalent up to an additive logarithmic  term. We show that the information distance is a universal cognitive similarity  distance. We investigate the maximal correlation of the shortest  programs involved, the maximal uncorrelation of programs (a generalization  of the Slepian-Wolf theorem of classical information theory), and the  density properties of the discrete metric spaces induced by the information  distances. A related distance measures the amount of nonreversibility of  a computation. Using the physical theo...
Soft Control on Collective Behavior of a Group of Autonomous Agents by a Shill Agent

Detecting design intent in approximate CAD models using symmetry.
Finding design intent embodied as high-level geometric relations between a CAD model’s sub-parts facilitates various tasks such as model editing and analysis. This is especially important for boundary-representation models arising from, e.g., reverse engineering or CAD data transfer. These lack explicit information about design intent, and often the intended geometric relations are only approximately present. The novel solution to this problem presented is based on detecting approximate local incomplete symmetries, in a hierarchical decomposition of the model into simpler, more symmetric sub-parts. Design intent is detected as congruencies, symmetries and symmetric arrangements of the leaf-parts in this decomposition. All elementary 3D symmetry types and common symmetric arrangements are considered. They may be present only locally in subsets of the leaf-parts, and may also be incomplete, i.e. not all elements required for a symmetry need be present. Adaptive tolerance intervals are detected automatically for matching interpoint distances, enabling efficient, robust and consistent detection of approximate symmetries. Doing so avoids finding many spurious relations, reliably resolves ambiguities between relations, and reduces inconsistencies. Experiments show that detected relations reveal significant design intent.
Representation of a Stochastic Traffic Bound.

Dynamic bandwidth partition schemes for integrated voice

Protein Secondary Structure Prediction Using NMR Chemical Shift Data.

A New Approach for Multi%2DDocument Update Summarization.

Detecting Market Trends by Ignoring It%2C Some Days.

Semi%2Dsupervised learning by disagreement.

Introduction to the special issue on %22data semantics for multimedia systems%22.

Context%2Daware fusion A case study on fusion of gait and face for human identification in video.

Exploiting remote learners in Internet environment with agents.

Foreword to the special issue on traffic modeling

Power spectrum of generalized Cauchy process.

Correlation matching method for the weak stationarity test of LRD traffic.

Power spectrum of generalized Cauchy process.



On supporting reliable QoS in multi%2Dhop multi%2Drate mobile ad hoc networks.

Pornprobe an LDA%2DSVM based pornography detection system.

A New Non%2DLinear Algorithm for 3D Reconstruction from Straight%2Dline Optical Flow.

Evolutionary Algorithm for the Radio Planning and Coverage Optimization of 3G Cellular Networks.

Autonomous System%2DBased Marking Scheme for Internet Traceback.

Optimal Allocation of Time%2DResources for Multihypothesis Activity%2DLevel Detection.

Constraint%2Daware event stream processing.

Interval event stream processing.

Pipelining%2DBased High Throughput Low Energy Mapping on Network%2Don%2DChip.

New Bounds on the Total%2DSquared%2DCorrelation of Quaternary Signature Sets and Optimal Designs.

R%2DCode Network Coding Based Reliable Broadcast in Wireless Mesh Networks with Unreliable Links.

New Greedy Algorithm for Computing Double%2DBase Chains.

Energy%2DEfficient Itinerary Planning for Mobile Agents in Wireless Sensor Networks.

Reconstructing Microwave Near%2DField Image Based on the Discrepancy of Radial Distribution of Dielectric Constant.

Fusion Segmentation Algorithm for SAR Images Based on HMT in Contourlet Domain and D%2DS Theory of Evidence.

Sequence Pattern Query Processing over Out%2Dof%2DOrder Event Streams.

Multi%2Ddocument Summarization by Information Distance.
Abstract—We are now living in a world where information is growing and updating quickly. Knowledge can be acquired more efficiently with the help of automatic document summarization and updating techniques. This paper describes a novel approach for multi-document update summarization. The best summary is defined as one of which has the minimal information distance to the entire document set. And the best update summary has the minimal conditional information distance to a document cluster given that a prior document cluster has already been read. We propose two methods to approximate information distance between two documents, one by compression and the other by the coding theory. Experiments on the DUC 2007 dataset 1 and the TAC 2008 dataset 2 have proved that our method closely correlates with the human-written summaries and outperforms LexRank in many categories under the ROUGE evaluation criterion.
Multi%2Ddocument Summarization by Information Distance.
Abstract—We are now living in a world where information is growing and updating quickly. Knowledge can be acquired more efficiently with the help of automatic document summarization and updating techniques. This paper describes a novel approach for multi-document update summarization. The best summary is defined as one of which has the minimal information distance to the entire document set. And the best update summary has the minimal conditional information distance to a document cluster given that a prior document cluster has already been read. We propose two methods to approximate information distance between two documents, one by compression and the other by the coding theory. Experiments on the DUC 2007 dataset 1 and the TAC 2008 dataset 2 have proved that our method closely correlates with the human-written summaries and outperforms LexRank in many categories under the ROUGE evaluation criterion.
Interactive Genetic Algorithms with Variational Population Size.

Learning instance specific distances using metric propagation.
In many real-world applications, such as image retrieval, it would be natural to measure the distances from one instance to others using instance specific distance which captures the distinctions from the perspective of the concerned instance. However, there is no complete framework for learning instance specific distances since existing methods are incapable of learning such distances for test instance and unlabeled data. In this paper, we propose the Isd method to address this issue. The key of Isd is metric propagation, that is, propagating and adapting metrics of individual labeled examples to individual unlabeled instances. We formulate the problem into a convex optimization framework and derive efficient solutions. Experiments show that Isd can effectively learn instance specific distances for labeled as well as unlabeled instances. The metric propagation scheme can also be used in other scenarios. 1.
Optimization Dispatch of Air Conditioner Loads Using Ant Colony Algorithm.

MRI%2Dcompatible hands%2Don cooperative control of a pneumatically actuated robot.

E%2DTec A Constraint%2DAware Query Engine for Pattern Detection over Event Streams.

Semantic Image Classification for Medical Videos.

Multi%2DLevel Virtual Ring Cross%2DLevel Name Routing with Embedded Identifier in Sensor Network.

GeoConnect Geographic and Connectivity%2DAware Routing Protocol for Wireless Sensor Network.

Robot path planning in uncertain environments based on particle swarm optimization.

Rules Driven Object%2DRelational Databases Ontology Learning.

Forest Vegetation Monitoring and Runoff in Water Supply Catchments Affected by Drying Climate.

Exploiting Multi%2DModal Interactions A Unified Framework.
Given an imagebase with tagged images, four types of tasks can be executed, i.e., content-based image retrieval, image annotation, text-based image retrieval, and query expansion. For any of these tasks the similarity on the concerned type of objects is essential. In this paper, we propose a framework to tackle these four tasks from a unified view. The essence of the framework is to estimate similarities by exploiting the interactions between objects of different modality. Experiments show that the proposed method can improve similarity estimation, and based on the improved similarity estimation, some simple methods can achieve better performances than some state-of-the-art techniques. 1
Modeling of One%2DCampus%2DID System Based on UML.

Use of active RFID and environment%2Dembedded sensors for indoor object location estimation.

A Dynamic Description Logic for UML.

Grocery shopping recommendations based on basket%2Dsensitive random walk.

Multimedia Evidence Fusion for Video Concept Detection via OWA Operator.

Block%2Dswitched Networks A New Paradigm for Wireless Transport.
TCP has well-known problems over multi-hop wireless networks as it conflates congestion and loss, performs poorly over time-varying and lossy links, and is fragile in the presence of route changes and disconnections. Our contribution is a clean-slate design and implementation of a wireless transport protocol, Hop, that uses reliable per-hop block transfer as a building block. Hop is 1) fast, because it eliminates many sources of overhead as well as noisy end-to-end rate control, 2) robust to partitions and route changes because of hop-by-hop control as well as in-network caching, and 3) simple, because it obviates complex end-to-end rate control as well as complex interactions between the transport and link layers. Our experiments over a 20-node multi-hop mesh network show that Hop is dramatically more efficient, achieving better fairness, throughput, delay, and robustness to partitions over several alternate protocols, including gains of more than an order of magnitude in median throughput. 1


A Particle Swarm Optimization Algorithm with Crossover for Resource Constrained Project Scheduling Problem.

A Network Coding Approach to Reliable Broadcast in Wireless Mesh Networks.

Specialized Review Selection for Feature Rating Estimation.

PICKY a novel SVD%2Dbased NMR spectra peak picking method.

A novel comprehensive wave%2Dform MS data processing method.

New left%2Dto%2Dright minimal weight signed%2Ddigit radix%2Dr representation.

SAR image segmentation based on mixture context and wavelet hidden%2Dclass%2Dlabel Markov random field.

On Supporting High%2DQuality 3D Geometry Multicasting over IEEE 802.11 Wireless Networks.

Minimum total%2Dsquared%2Dcorrelation quaternary signature sets new bounds and optimal designs.

PRESTO feedback%2Ddriven data management in sensor networks.
This paper presents PRESTO, a novel two-tier sensor data management architecture comprising proxies and sensors that cooperate with one another for acquiring data and processing queries. PRESTO proxies construct time-series models of observed trends in the sensor data and transmit the parameters of the model to sensors. Sensors check sensed data with model-predicted values and transmit only deviations from the predictions back to the proxy. Such a model-driven push approach is energyefficient, while ensuring that anomalous data trends are never missed. In addition to supporting queries on current data, PRESTO also supports queries on historical data using interpolation and local archival at sensors. PRESTO can adapt model and system parameters to data and query dynamics to further extract energy savings. We have implemented PRESTO on a sensor testbed comprising Intel Stargates and Telos Motes. Our experiments show that in a temperature monitoring application, PRESTO yields one to two orders of magnitude reduction in energy requirements over on-demand, proactive or model-driven pull approaches. PRESTO also results in an order of magnitude reduction in query latency in a 1 % duty-cycled five hop sensor network over a system that forwards all queries to remote sensor nodes.
Editorial.
calls &amp; calendarEDITORIAL
IPSA a novel architecture design for integrating IP and sensor networks.

Semi%2Dsupervised document retrieval.

Predicting Local Quality of a Sequence%2DStructure Alignment.

Preface.
part of a series of studies in support of the California Governor’s Advisory Committee on Education Excellence. i PREFACE i LIST OF FIGURES iv
Can We Determine a Protein Structure Quickly%3F


Image%2Fvideo%2Dbased pattern analysis and HCI applications.

Mining extremely small data sets with application to software reuse.

On two open problems of 2%2Dinterval patterns.

Finding compact structural motifs.
Abstract. Multiple structural alignment is a fundamental problem in computational biology. Compared with sequence alignment, structural alignment is more powerful in detecting the evolutionary relationship of proteins. A variety of algorithms have been proposed to attack this problem, however, they are either heuristic without theoretical performance guarantee, or inefficient for employing an exhaustive search strategy. Here, we study a reasonably restricted version of this problem: compact structural motif problem. In this paper, we prove that this restricted version is still NP-Hard, and present a polynomial-time approximation scheme to solve it. To our knowledge, this is the first time that approximation algorithms with guaranteed ratio are presented for multiple structural alignment. 1 Introduction Identifying structural motifs for proteins is a fundamental problem in computa-tional biology. It has been widely accepted that during the evolution of proteins, structures are more conserved than sequences. In addition, structural motifs arethought to be tightly related to protein functions[1]. Thus, identifying the common substructures from a set of proteins can help us to know their evolutionaryhistory and functions. With a rapid growth in the number of the structures in Protein Data Bank(PDB) and protein folding methods, the need for fast andaccurate structural comparison methods has become more and more crucial. Multiple structural motif finding is the structural analogue of the sequencemotif finding problem. For the former problem, the input consists of a set of protein structures in three-dimensional space, R3. The objective is to find a setof substructures, one from each protein, that exhibit the highest degree of similarity. Roughly speaking, there are two main methods to measure the structuresimilarity, i.e., coordinate root mean squared deviation(cRMS) and distance root mean squared deviation(dRMS). The first ones calculate the internal distancefor each protein first, and compare these internal distance matrix for the input
On Design of Oligonucleotide SNP Arrays and Methods for Genotype Calling.


Information shared by many objects.

Finding Largest Well%2DPredicted Subset of Protein Structure Models.

Online Manifold Regularization A New Learning Setting and Empirical Study.
Abstract. We consider a novel “online semi-supervised learning ” setting where (mostly unlabeled) data arrives sequentially in large volume, and it is impractical to store it all before learning. We propose an online manifold regularization algorithm. It differs from standard online learning in that it learns even when the input point is unlabeled. Our algorithm is based on convex programming in kernel space with stochastic gradient descent, and inherits the theoretical guarantees of standard online algorithms. However, naïve implementation of our algorithm does not scale well. This paper focuses on efficient, practical approximations; we discuss two sparse approximations using buffering and online random projection trees. Experiments show our algorithm achieves risk and generalization accuracy comparable to standard batch manifold regularization, while each step runs quickly. Our online semi-supervised learning setting is an interesting direction for further theoretical development, paving the way for semi-supervised learning to work on real-world lifelong learning tasks. 1
An Immune Algorithm%2DBased Atmospheric Quality Assessment Model and Its Applications.

Event dissemination via group%2Daware stream filtering.
We consider a distributed system that disseminates highvolume event streams to many simultaneous monitoring applications over a low-bandwidth network. For bandwidth efficiency, we propose a group-aware stream filtering approach, used together with multicasting, that exploits two overlooked, yet important, properties of monitoring applications: 1) many of them can tolerate some degree of “slack” in their data quality requirements, and 2) there may exist multiple subsets of the source data satisfying the quality needs of an application. We can thus choose the “best alternative” subset for each application to maximize the data overlap within the group to best benefit from multicasting. Here we provide a general framework for the group-aware stream filtering problem, which we prove is NP-hard. We introduce a suite of heuristics-based algorithms that ensure data quality (specifically, granularity and timeliness) while preserving bandwidth. Our evaluation shows that groupaware stream filtering is effective in trading CPU time for bandwidth savings, compared with self-interested filtering. 1.
Online Manifold Regularization A New Learning Setting and Empirical Study.
Abstract. We consider a novel “online semi-supervised learning ” setting where (mostly unlabeled) data arrives sequentially in large volume, and it is impractical to store it all before learning. We propose an online manifold regularization algorithm. It differs from standard online learning in that it learns even when the input point is unlabeled. Our algorithm is based on convex programming in kernel space with stochastic gradient descent, and inherits the theoretical guarantees of standard online algorithms. However, naïve implementation of our algorithm does not scale well. This paper focuses on efficient, practical approximations; we discuss two sparse approximations using buffering and online random projection trees. Experiments show our algorithm achieves risk and generalization accuracy comparable to standard batch manifold regularization, while each step runs quickly. Our online semi-supervised learning setting is an interesting direction for further theoretical development, paving the way for semi-supervised learning to work on real-world lifelong learning tasks. 1


A Novel Multi%2Dreduced SVM Approach for Speaker Recognition.

Application of Improved Algorithm of Data Reduction to Knowledge Discovery of Information Security Management.

A Comment on %22Constructing Regularity Feature Trees for Solid Models%22.
In the feature subset selection problem, a learning algorithm is faced with the problem of selecting a relevant subset of features upon which to focus its attention, while ignoring the rest. To achieve the best possible performance with a particular learning algorithm on a particular domain, a feature subset selection method should consider how the algorithm and the training data interact. We explore the relation between optimal feature subset selection and relevance. Our wrapper method searches for an optimal feature subset tailored to a particular algorithm and a domain. We study the strengths and weaknesses of the wrapper approach and show improvements over the original design. We compare the wrapper approach to induction without feature subset selection and to Relief, a filter-based approach to feature subset selection. Significant improvement in accuracy on real problems is achieved for the two families of induction algorithms used: decision trees and Naive-Bayes.
QOAR Adaptive QoS Scheme in Multi%2DRate Wireless LANs.

Distributed Topology Control in Multi%2DChannel Multi%2DRadio Mesh Networks.

Dynamic Budget Partition Scheme for Integrated Voice%2FVideo%2FData Traffic in the IEEE 802.11e WLANs.


Remaining Delivery Time Estimation Based Routing for Intermittently Connected Mobile Networks.

Personalized event%2Dbased news video retrieval with dynamic user%2Dlog.

A Context%2Daware Computational Trust Model for Multi%2Dagent Systems.


ELF A Constraint%2DAware XQuery Engine for Processing XML Streams with Minimized Memory Footprint.
[G5] [G6] [G7] [G8] [G9] NSF, SGER ($120,327 from Sep 2009 – May 2011), Towards a Generic Provenance Metadata
Efficiently loading and processing XML streams.
[G5] [G6] [G7] [G8] [G9] NSF, SGER ($120,327 from Sep 2009 – May 2011), Towards a Generic Provenance Metadata
Adaptive Frame Concatenation Mechanisms for QoS in Multi%2DRate Wireless Ad Hoc Networks.

Fast%2Dscale period%2Ddoubling bifurcation in voltage%2Dmode controlled full%2Dbridge inverter.

Medical Video Event Classification Using Shared Features.

A Semantics%2D and Data%2DDriven SOA for Biomedical Multimedia Systems.

Designing succinct structural alphabets.

Robotic System for Transapical Aortic Valve Replacement with MRI Guidance.

The Use of Configuration Conception in Software Development.

Mining Bulletin Board Systems Using Community Generation.

R%2DMap Mapping Categorical Data for Clustering and Visualization Based on Reference Sets.

Synopsis Alignment Importing External Text Information for Multi%2Dmodel Movie Analysis.
Abstract. Text information, which plays important role in news video concept detection, has been ignored in state-of-the-art movie analysis technology. It is so because movie subtitles are speech of roles which do not directly describe content of movie and contributes little to movie analysis. In this paper, we import collaborative-editing synopsis from professional movie sites for movie analysis, which gives detailed descriptive text of movie. Two aligning methods, subtitle alignment and RoleNet alignment, are proposed complementarily to align synopsis to movie to get scene-level text information of movie. The experiment show that proposed methods can effectively align synopsis to movie scene and the imported text information can give a more user-preferred summarization than merely using audiovisual feature.
Rapid and Accurate Protein Side Chain Prediction with Local Backbone Information.

The value of personalised recommender systems to e%2Dbusiness a case study.

TRECVID 2008 Participation by MCG%2DICT%2DCAS.

Cross%2DLayer and Path Priority Scheduling Based Real%2DTime Video Communications over Wireless Sensor Networks.

Adaptive Fusion of Gait and Face for Human Identification in Video.

Dynamic Bandwidth Partition with Finer%2DTune %28DP%2DFT%29 Scheme for Multimedia IEEE 802.11e WLANs.

Nearest Neighbor Interchange and Related Distances.

ZOOM%21 Zillions of oligos mapped.

Normalized Information Distance
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practical application is called ‘normalized compression distance’ and it is trivially computable. It is a parameter-free similarity measure based on compression, and is used in pattern recognition, data mining, phylogeny, clustering, and classification. The complexity properties of its theoretical precursor, the NID, have been open. We show that the NID is neither upper semicomputable nor lower semicomputable up to any reasonable precision.  
Detecting approximate symmetries of discrete point subsets.
Detecting approximate symmetries of parts of a model is important when attempting to determine the geometrical design intent of approximate boundary-representation (B-rep) solid models produced e.g. by reverse engineering systems. For example, such detected symmetries may be enforced exactly on the model to improve its shape, to simplify its analysis, or to constrain it during editing. We give an algorithm to detect local approximate symmetries in a discrete point set derived from a B-rep model: the output comprises the model’s potential local symmetries at various automatically detected tolerance levels. Non-trivial symmetries of subsets of the point set are found as unambiguous permutation cycles, i.e. vertices of an approximately regular polygon or an anti-prism, which are sufficiently separate from other points in the point set. The symmetries are detected using a rigorous, tolerance-controlled, incremental approach, which expands symmetry seed sets by one point at a time. Our symmetry cycle detection approach only depends on inter-point distances. The algorithm takes time O(n 4) where n is the number of input points. Results produced by our algorithm are demonstrated using a variety of examples.
Processing recursive XQuery over XML streams The Raindrop approach.
[G5] [G6] [G7] [G8] [G9] NSF, SGER ($120,327 from Sep 2009 – May 2011), Towards a Generic Provenance Metadata
Automatic Language Identification with Discriminative Language Characterization Based on SVM.

Melody Track Selection Using Discriminative Language Model.

Group%2Daware stream filtering for bandwidth%2Defficient data dissemination.
{ mingli, dfk} at cs.dartmouth.edu In this paper 1 we are concerned with disseminating high-volume data streams to many simultaneous applications over a low-bandwidth wireless mesh network. For bandwidth efficiency, we propose a group-aware stream filtering approach, used in conjunction with multicasting, that exploits two overlooked, yet important, properties of these applications: 1) many applications can tolerate some degree of “slack ” in their data quality requirements, and 2) there may exist multiple subsets of the source data satisfying the quality needs of an application. We can thus choose the “best alternative ” subset for each application to maximize the data overlap within the group to best benefit from multicasting. An evaluation of our prototype implementation shows that group-aware data filtering can save bandwidth with low CPU overhead. We also analyze the key factors that affect its performance, based on testing with heterogeneous filtering requirements.
Mango Multiple Alignment with n Gapped Oligos.
Multiple sequence alignment is a classical and challenging task for biological sequence analysis. The problem is NP-hard. The full dynamic programming takes too much time. The progressive alignment heuristics adopted by most state of the art multiple sequence alignment programs suffer from the ‘once a gap, always a gap ’ phenomenon. Is there a radically new way to do multiple sequence alignment? This paper introduces a novel and orthogonal multiple sequence alignment method, using multiple optimized spaced seeds and new algorithms to handle these seeds efficiently. Our new algorithm processes information of all sequences as a whole, avoiding problems caused by the popular progressive approaches. Because the optimized spaced seeds are provably significantly more sensitive than the consecutive k-mers, the new approach promises to be more accurate and reliable. To validate our new approach, we have implemented MANGO: Multiple Alignment with N Gapped Oligos. Experiments were carried out on large 16S RNA benchmarks showing that MANGO compares favorably, in both accuracy and speed, against state-of-art multiple sequence alignment methods, including ClustalW 1.83, MUSCLE 3.6, MAFFT 5.861, Prob-ConsRNA 1.11, Dialign 2.2.1, DIALIGN-T 0.2.1, T-Coffee 4.85, POA 2.0 and Kalign 2.0. MANGO is available at
Cryptanalysis of a Type of CRT%2DBased RSA Algorithms.
Let n = pq denote the RSA modulus with two primes p and q, e the public key and d the corresponding private key, so that ed ≡ 1 (mod ϕ(n)), where the Euler Totient of n is ϕ(n)  = (p − 1)(q − 1). Let f(x) denote the faulty value on a variable x if an error occurs during the computation of x, and l(x) be the length of x in bits.
New Information Distance Measure and Its Application in Question Answering System.

Accelerated Kernel CCA plus SVDD A Three%2Dstage Process for Improving Face Recognition.

Data%2Dcentric middleware for context%2Daware pervasive computing.
The complexity of developing and deploying context-aware pervasive-computing applications calls for distributed software infrastructures that assist applications to collect, aggregate, and disseminate contextual data. In this paper, we motivate a data-centric design for such an infrastructure to support context-aware applications. Our middleware system, Solar, treats contextual data sources as stream publishers and the core of Solar is a scalable and self-organizing peer-to-peer overlay to support data-driven services. We present how different services could be systematically integrated on top of the Solar overlay. We also discuss our experience and lessons learned when using Solar to support several implemented scenarios. We conclude that a data-centric infrastructure is necessary to facilitate both development and deployment of pervasive-computing applications.
Cross%2Dlayer Resource Control to Improve TCP Performance over Wireless Network.

On supporting high quality 3D geometry multicasting over IEEE 802.11 wireless networks.

Towards Developing a Web%2Dbased Gap Management Information System for Cucumber in China.

Expert System of Non%2Dpollution Feicheng Peach Production in China.

Towards Developing an Early Warning System for Cucumber Diseases for Greenhouse in China.

A Context%2DAware Trust Establishment and Mapping Framework for Web Applications.

Finding Compact Structural Motifs.
Abstract. Multiple structural alignment is a fundamental problem in computational biology. Compared with sequence alignment, structural alignment is more powerful in detecting the evolutionary relationship of proteins. A variety of algorithms have been proposed to attack this problem, however, they are either heuristic without theoretical performance guarantee, or inefficient for employing an exhaustive search strategy. Here, we study a reasonably restricted version of this problem: compact structural motif problem. In this paper, we prove that this restricted version is still NP-Hard, and present a polynomial-time approximation scheme to solve it. To our knowledge, this is the first time that approximation algorithms with guaranteed ratio are presented for multiple structural alignment. 1 Introduction Identifying structural motifs for proteins is a fundamental problem in computa-tional biology. It has been widely accepted that during the evolution of proteins, structures are more conserved than sequences. In addition, structural motifs arethought to be tightly related to protein functions[1]. Thus, identifying the common substructures from a set of proteins can help us to know their evolutionaryhistory and functions. With a rapid growth in the number of the structures in Protein Data Bank(PDB) and protein folding methods, the need for fast andaccurate structural comparison methods has become more and more crucial. Multiple structural motif finding is the structural analogue of the sequencemotif finding problem. For the former problem, the input consists of a set of protein structures in three-dimensional space, R3. The objective is to find a setof substructures, one from each protein, that exhibit the highest degree of similarity. Roughly speaking, there are two main methods to measure the structuresimilarity, i.e., coordinate root mean squared deviation(cRMS) and distance root mean squared deviation(dRMS). The first ones calculate the internal distancefor each protein first, and compare these internal distance matrix for the input
Information Distance from a Question to an Answer.

Multi%2DAgent System%2Dbased Hierarchy Grid Middleware.

Finding Compact Structural Motifs.
Abstract. Multiple structural alignment is a fundamental problem in computational biology. Compared with sequence alignment, structural alignment is more powerful in detecting the evolutionary relationship of proteins. A variety of algorithms have been proposed to attack this problem, however, they are either heuristic without theoretical performance guarantee, or inefficient for employing an exhaustive search strategy. Here, we study a reasonably restricted version of this problem: compact structural motif problem. In this paper, we prove that this restricted version is still NP-Hard, and present a polynomial-time approximation scheme to solve it. To our knowledge, this is the first time that approximation algorithms with guaranteed ratio are presented for multiple structural alignment. 1 Introduction Identifying structural motifs for proteins is a fundamental problem in computa-tional biology. It has been widely accepted that during the evolution of proteins, structures are more conserved than sequences. In addition, structural motifs arethought to be tightly related to protein functions[1]. Thus, identifying the common substructures from a set of proteins can help us to know their evolutionaryhistory and functions. With a rapid growth in the number of the structures in Protein Data Bank(PDB) and protein folding methods, the need for fast andaccurate structural comparison methods has become more and more crucial. Multiple structural motif finding is the structural analogue of the sequencemotif finding problem. For the former problem, the input consists of a set of protein structures in three-dimensional space, R3. The objective is to find a setof substructures, one from each protein, that exhibit the highest degree of similarity. Roughly speaking, there are two main methods to measure the structuresimilarity, i.e., coordinate root mean squared deviation(cRMS) and distance root mean squared deviation(dRMS). The first ones calculate the internal distancefor each protein first, and compare these internal distance matrix for the input

Computing Exact p%2DValue for Structured Motif.


Information Distance and Applications.

B%2Dcell Epitope Mapping of Helicobacter pylori Neutrophil%2DActivating Protein.

SAR Image Segmentation Based on Mixture Context and Wavelet Hidden%2DClass%2DLabel Markov Random Field.

Speaker Identification Based on Multi%2Dreduced SVM.

Centralized Scheduling Tree Construction Under Multi%2DChannel IEEE 802.16 Mesh Networks.

A Local%2DInformation%2DBased Blind Image Restoration Algorithm Using a MLP.

Group%2Daware Stream Filtering.
In this paper we are concerned with disseminating high-volume data streams to many simultaneous context-aware applications over a low-bandwidth wireless mesh network. For bandwidth efficiency, we propose a group-aware stream filtering approach, used in conjunction with multicasting, that exploits two overlooked, yet important, properties of these applications: 1) many applications can tolerate some degree of “slack ” in their data quality requirements, and 2) there may exist multiple subsets of the source data satisfying the quality needs of an application. We can thus choose the “best alternative” subset for each application to maximize the data overlap within the group to best benefit from multicasting. An evaluation of our prototype implementation shows that group-aware data filtering can save bandwidth with low CPU overhead.
Event Stream Processing with Out%2Dof%2DOrder Data Arrival.
[G5] [G6] [G7] [G8] [G9] NSF, SGER ($120,327 from Sep 2009 – May 2011), Towards a Generic Provenance Metadata
Invited Talk Modern Homology Search.

Homology search for genes.
Motivation: Life science researchers often require an exhaustive list of protein coding genes similar to a given query gene. To find such genes, homology search tools, such as BLAST or PatternHunter, return a set of high-scoring pairs (HSPs). These HSPs then need to be correlated with existing sequence annotations, or assembled manually into putative gene structures. This process is error-prone and labor-intensive, especially in genomes without reliable gene annotation. Results: We have developed a homology search solution that automates this process, and instead of HSPs returns complete gene structures. We achieve better sensitivity and specificity by adapting a hidden Markov model for gene finding to reflect features of the query gene. Compared to traditional homology search, our novel approach identifies splice sites much more reliably and can even locate exons that were lost in the query gene. On a testing set of 400 mouse query genes, we report 79 % exon sensitivity and 80 % exon specificity in the human genome based on orthologous genes annotated in NCBI HomoloGene. In the same set, we also found 50 (12%) gene structures with better protein alignment scores than the ones identified in HomoloGene. Availability: The Java implementation is available for download from
Generating Traffic Time Series Based on Generalized Cauchy Process.

Towards Describing Multi%2Dfractality of Traffic Using Local Hurst Function.

A Novel Description of Multifractal Phenomenon of Network Traffic Based on Generalized Cauchy Process.

A Question Understanding Model Based on Knowledge Points for Chinese Question Answering Service in E%2DLearning.

Information distance from a question to an answer.

Classification Rule Acquisition Based on Extended Concept Lattice.

Model for Survivability of Wireless Sensor Network.

Application of Discrimination Degree for Attributes Reduction in Concept Lattice.

ROBOTRAK a centralized real%2Dtime monitoring

A probabilistic model for item%2Dbased recommender systems.

Wide%2Dw%2DNAF Method for Scalar Multiplication on K%F6blitz Curves.

Security Analysis of wrNAF and SPA Resistant Scalar Multiplication.

Security Analysis and Improvement of a %28%24t

Multi%2Duser data sharing in radar sensor networks.

Multi%2Duser data sharing in radar sensor networks.

Detecting approximate incomplete symmetries in discrete point sets.
Motivated by the need to detect design intent in approximate boundary representation models, we give an algorithm to detect incomplete symmetries of discrete points, giving the models ’ potential local symmetries at various automatically detected tolerances. Here, incomplete symmetry is defined as a set of incomplete cycles which are constructed by, e.g., a set of consecutive vertices of an approximately regular polygon, induced by a single isometry. All seven 3D elementary isometries are considered for symmetry detection. Incomplete cycles are first found using a tolerance-controlled point expansion approach. Subsequently, these cycles are clustered for incomplete symmetry detection. The resulting clusters have welldefined, unambiguous approximate symmetries suitable for design intent detection, as demonstrated experimentally.
TRECVID 2007 High%2DLevel Feature Extraction By MCG%2DICT%2DCAS.

Multiple features data fusion method in color texture analysis.

Multi%2Dinnovation least squares identification methods based on the auxiliary model for MISO systems.

Computing exact P%2Dvalues for DNA motifs.
Motivation: Many heuristic algorithms have been designed to approximate p-values of DNA motifs described by position weight matrices, for evaluating their statistical significance. They often significantly deviate from the true p-value by orders of magnitude. Exact p-value computation is needed for ranking the motifs. Furthermore, surprisingly, the complexity of the problem is unknown. Results: We show the problem to be NP-hard, and present MotifRank, software based on dynamic programming, to calculate exact p-values of motifs. We define the exact pvalue on a general and more precise model. Asymptotically, MotifRank is faster than the best exact p-value computing algorithm, and is in fact practical. Our experiments clearly demonstrate that MotifRank significantly improves the accuracy of existing approximation algorithms.
DNA as active polymer long%2Drange allosteric effect and chromatin loop structure.

Semisupervised Regression with Cotraining%2DStyle Algorithms.

Spatial Motion Constraints Using Virtual Fixtures Generated by Anatomy.

Predicting Future Customers via Ensembling Gradually Expanded Trees.

Improve Computer%2DAided Diagnosis With Machine Learning Techniques Using Undiagnosed Samples.
 In computer-aided diagnosis, machine learning techniques have been widely applied to learn hypothesis from diagnosed samples in order to assist the medical experts in making diagnosis. To learn a well-performed hypothesis, a large amount of diagnosed samples are required. Although the samples can be easily collected from routine medical examinations, it is usually impossible for the medical experts to make diagnosis for each of the collected samples. If hypothesis could be learned in presence of a large amount of undiagnosed samples, the heavy burden on the medical experts could be released. In this paper, a new semi-supervised learning algorithm named Co-Forest is proposed. It extends the co-training paradigm by using a well-known ensemble method named Random Forest, which enables Co-Forest to estimate the labeling confidence of undiagnosed samples and produce the final hypothesis easily. Experiments on benchmark data sets verify the effectiveness of the proposed algorithm. Case studies on three medical data sets and a successful application to microcalcification detection for breast cancer diagnosis show that undiagnosed samples are helpful in building computer-aided diagnosis systems, and Co-Forest is able to enhance the performance of the hypothesis learned on only a small amount of diagnosed samples by utilizing the available undiagnosed samples. 
Predicting Future Customers via Ensembling Gradually Expanded Trees.

On the complexity of the spaced seeds.
Optimal spaced seeds were introduced by the theoretical computer science community to bioinformatics to effectively increase homology search sensitivity. They are now serving thousands of homology search queries daily. While dozens of papers have been published on optimal spaced seeds since their invention, many fundamental questions still remain unanswered. In this paper, we settle several open questions in this area. Specifically, we prove that when the length of a non-uniformly spaced seed is bounded by an exponential function of the seed weight, the seed outperforms strictly the traditional consecutive seed in both (i) the average number of non-overlapping hits and (ii) the asymptotic hit probability. Then, we study the computation of the hit probability of a spaced seed, solving three more open questions: (iii) hit probability computation in a uniform homologous region is NP-hard and (iv) it admits a PTAS; (v) the asymptotic hit probability is computable in exponential time in seed length, independent of the homologous region length. 1
Average%2Dcase analysis of QuickSort and Binary Insertion Tree height using incompressibility.

Information Distance and its Applications.

Near optimal multiple alignment within a band in polynomial time.
Multiple sequence alignment is one of the most important problems in computational biology. Because of its notorious difficulties, aligning sequences within a constant band is a popular practice in bioinformatics with good results [17; 13; 14; 15; 1; 3; 6; 20; 18]. However, the problem is still NP-hard for multiple sequences. In this paper, we present polynomial time approximation schemes (PTAS) for multiple sequence alignment within a constant band, under standard models of SP alignment and consensus (star) alignment. The algorithms work for very general score schemes. In order to prove our main results, we also present a PTAS for SP alignment and a PTAS for consensus alignment, allowing only constant number of insertion and deletion gaps (of arbitrary length) per sequence on the average.  1. 
Special issue on computational molecular biology.
An information theory based multiple alignment (&#034;Malign&#034;) method was used to align the DNA binding sequences of the OxyR and Fis proteins, whose sequence conservation is so spread out that it is difficult to identify the sites. In the algorithm described here, the information content of the sequences is used as a unique global criterion for the quality of the alignment. The algorithm uses look-up tables to avoid recalculating computationally expensive functions such as the logarithm. Because there are no arbitrary constants and because the results are reported in absolute units (bits), the best alignment can be chosen without ambiguity. Starting from randomly selected alignments, a hill-climbing algorithm can track through the immense space of s  n  combinations where s is the number of sequences and n is the number of positions possible for each sequence. Instead of producing a single alignment, the algorithm is fast enough that one can afford to use many start points and to classify ...
On the complexity of the spaced seeds.
Optimal spaced seeds were introduced by the theoretical computer science community to bioinformatics to effectively increase homology search sensitivity. They are now serving thousands of homology search queries daily. While dozens of papers have been published on optimal spaced seeds since their invention, many fundamental questions still remain unanswered. In this paper, we settle several open questions in this area. Specifically, we prove that when the length of a non-uniformly spaced seed is bounded by an exponential function of the seed weight, the seed outperforms strictly the traditional consecutive seed in both (i) the average number of non-overlapping hits and (ii) the asymptotic hit probability. Then, we study the computation of the hit probability of a spaced seed, solving three more open questions: (iii) hit probability computation in a uniform homologous region is NP-hard and (iv) it admits a PTAS; (v) the asymptotic hit probability is computable in exponential time in seed length, independent of the homologous region length. 1
Applications of algorithmic information theory.
Two philosophical applications of the concept of program-size complexity are discussed. First, we consider the light program-size complexity sheds on whether mathematics is invented or discovered, i.e., is empirical or is apriori. Second, we propose that the notion of algorithmic independence sheds light on the question of being and how the world of our experience can be partitioned into separate entities.
ONBRIRES Ontology%2DBased Biological Relation Extraction System.

A Real%2DTime and Reliable Approach to Detecting Traffic Variations at Abnormally High and Low Rates.

Generation of Comprehensible Hypotheses from Gene Expression Data.

Information Distance and Its Applications.

DyXY a proximity congestion%2Daware deadlock%2Dfree dynamic routing method for network on chip.

Constructing Regularity Feature Trees for Solid Models.
Approximate geometric models, e.g. as created by reverse engineering, describe the approximate shape of an object, but do not record the underlying design intent. Automatically inferring geometric aspects of the design intent, represented by feature trees and geometric constraints, enhances the utility of such models for downstream tasks. One approach to design intent detection in such models is to decompose them into regularity features. Geometric regularities such as symmetries may then be sought in each regularity feature, and subsequently be combined into a global, consistent description of the model’s geometric design intent. This paper describes a systematic approach for finding such regularity features based on recovering broken symmetries in the model. The output is a tree of regularity features for subsequent use in regularity detection and selection. Experimental results are given to demonstrate the operation and efficiency of the algorithm.
Information distance.
While Kolmogorov complexity is the accepted absolute measure of information  content in an individual finite object, a similarly absolute notion  is needed for the information distance between two individual objects, for  example, two pictures. We give several natural definitions of a universal  information metric, based on length of shortest programs for either ordinary  computations or reversible (dissipationless) computations. It turns  out that these definitions are equivalent up to an additive logarithmic  term. We show that the information distance is a universal cognitive similarity  distance. We investigate the maximal correlation of the shortest  programs involved, the maximal uncorrelation of programs (a generalization  of the Slepian-Wolf theorem of classical information theory), and the  density properties of the discrete metric spaces induced by the information  distances. A related distance measures the amount of nonreversibility of  a computation. Using the physical theo...
Mining Frequent Patterns based on Compressed FP%2Dtree without Conditional FP%2Dtree Generation.

Developing Personalized Knowledge Navigation Service for Students Self%2DLearning based on Interpretive Structural Modeling.

Processing Recursive XQuery over XML Streams The Raindrop Approach.
[G5] [G6] [G7] [G8] [G9] NSF, SGER ($120,327 from Sep 2009 – May 2011), Towards a Generic Provenance Metadata
Chaotically Masking Traffic Pattern to Prevent Traffic Pattern Analysis Attacks for Mission Critical Applications in Computer Communication Networks.

An Experimental Study on Automatic Face Gender Classification.
This paper presents an experimental study on automatic face gender classification by building a system that mainly consists of four parts, face detection, face alignment, texture normalization and gender classification. Comparative study on the effects of different texture normalization methods including two kinds of affine mapping and one Delaunay triangulation based warping as preprocesses for gender classification by SVM, LDA and Real Adaboost respectively is reported through experiments on very large sets of snapshot images. 1.
Constrained Control for Surgical Assistant Robots.

A Novel Audio Watermarking in Wavelet Domain.

Representation Interest Point Using Empirical Mode Decomposition and Independent Components Analysis.

An Efficient Wrapper Scan Chain Configuration Method for Network%2Don%2DChip Testing.

An Improved OIF Elman Neural Network and Its Applications to Stock Market.

From Three Ideas in TCS to Three Applications in Bioinformatics.

From Three Ideas in TCS to Three Applications in Bioinformatics.

PRESTO Feedback%2Ddriven Data Management in Sensor Networks.
This paper presents PRESTO, a novel two-tier sensor data management architecture comprising proxies and sensors that cooperate with one another for acquiring data and processing queries. PRESTO proxies construct time-series models of observed trends in the sensor data and transmit the parameters of the model to sensors. Sensors check sensed data with model-predicted values and transmit only deviations from the predictions back to the proxy. Such a model-driven push approach is energyefficient, while ensuring that anomalous data trends are never missed. In addition to supporting queries on current data, PRESTO also supports queries on historical data using interpolation and local archival at sensors. PRESTO can adapt model and system parameters to data and query dynamics to further extract energy savings. We have implemented PRESTO on a sensor testbed comprising Intel Stargates and Telos Motes. Our experiments show that in a temperature monitoring application, PRESTO yields one to two orders of magnitude reduction in energy requirements over on-demand, proactive or model-driven pull approaches. PRESTO also results in an order of magnitude reduction in query latency in a 1 % duty-cycled five hop sensor network over a system that forwards all queries to remote sensor nodes.
Image Classification Via LZ78 Based String Kernel A Comparative Study.

Superiority and complexity of the spaced seeds.
Optimal spaced seeds were introduced by the theoretical computer science community to bioinformatics to effectively increase homology search sensitivity. They are now serving thousands of homology search queries daily. While dozens of papers have been published on optimal spaced seeds since their invention, many fundamental questions still remain unanswered. In this paper, we settle several open questions in this area. Specifically, we prove that when the length of a non-uniformly spaced seed is bounded by an exponential function of the seed weight, the seed outperforms strictly the traditional consecutive seed in both (i) the average number of non-overlapping hits and (ii) the asymptotic hit probability. Then, we study the computation of the hit probability of a spaced seed, solving three more open questions: (iii) hit probability computation in a uniform homologous region is NP-hard and (iv) it admits a PTAS; (v) the asymptotic hit probability is computable in exponential time in seed length, independent of the homologous region length. 1
R%2DSOX Runtime Semantic Query Optimization over XML Streams.

On the Complexity of the Crossing Contact Map Pattern Matching Problem.

Bifurcations of travelling wave solutions in a class of generalized KdV equation.

Quadratic approximation to plane parametric curves and its application in approximate implicitization.

Change trend of averaged Hurst parameter of traffic under DDOS flood attacks.
Abstract:- Information integrity of communication data is crucial to e-business systems. An adversary may delete or insert packets into a normal communication data series in e-business systems to destroy information integrity to produce deserters (likely informal, this paper uses the term tamped type attacks to specifically describe those that attackers detect or insert packets into a normal data series). Consequently, a security issue in an e-business system is how to detect tamped type attacks. From a view of intrusion detection systems, statistic methods of intrusion detection are increasingly paid attention to [1-3]. This short paper gives a method for statistically real-time detection of tampered type attacks. The method is based on power spectra of monitored traffic time series with finite length. The detection probability is derived. A case study is demonstrated with a real-traffic series to suggest that the present method can be used to give an alarm at the early stage of intrusions. Key-Words:- Network-based IDS, anomaly intrusion detection, information integrity, pattern matching 1
A hybrid method for relation extraction from biomedical literature.

Prima Peptide Robust Identification from Ms%2Fms Spectra.

Optimizing Multiple Spaced Seeds for Homology Search.
Abstract. Optimized spaced seeds improve sensitivity and specificity in localhomology search [1]. Recently, several authors [2-4] have shown that multiple seeds can have better sensitivity and specificity than single seeds. We describea linear programming-based algorithm to optimize a set of seeds. Our algorithm offers a performance guarantee: the sensitivity of a chosen seed set is at least 70%of what can be achieved, in most reasonable models of homologous sequences. Our method achieves performance comparable to that of a greedy algorithm, butour work gives this area a mathematical foundation.
Middleware for streaming 3D progressive meshes over lossy networks.

Quadratic approximation to plane parametric curves and its application in approximate implicitization.

End%2Dto%2Dend QoS framework for heterogeneous wired%2Dcum%2Dwireless networks.
With information access becoming more and more ubiquitous, there is a need for providing QoS support for communication that spans wired and wireless networks. For the wired side, RSVP/SBM has been widely accepted as a flow reservation scheme in IEEE 802 style LANs. Thus, it would be desirable to investigate the integration of RSVP and a flow reservation scheme in wireless LANs, as an end-to-end solution for QoS guarantee in wiredcum-wireless networks. For this purpose, we propose WRESV, a lightweight RSVP-like flow reservation and admission control scheme for IEEE 802.11 wireless LANs. Using WRESV, wired/wireless integration can be easily implemented by cross-layer interaction at the Access Point. Main components of the integration are RSVP-WRESV parameter mapping and the initiation of new reservation messages, depending on where senders/receivers are located. In addition, to support smooth roaming of mobile users among different basic service sets (BSS), we devise an efficient handoff scheme that considers both the flow rate demand and network resource availability for continuous QoS support. Furthermore, various optimizations for supporting multicast session and QoS re-negotiation are proposed for better performance improvement. Extensive simulation results show that the proposed scheme is promising in enriching the QoS support of multimedia applications in heterogeneous wired-cum-wireless networks. 1.
Approximation of Class Unions Based on Dominance%2DMatrix Within Dominance%2DBased Rough Set Approach.

An LZ78 Based String Kernel.
We develop the notion of normalized information distance (NID) [7] into a kernel distance suitable for use with a Support Vector Machine classifier, and demonstrate its use for an audio genre classification task. Our classification scheme involves a relatively small number of low-level audio features, is efficient to compute, yet generates an accuracy which compares well with recent works.
PRIME Peptide robust identification from MS%2FMS spectra.

Consensus fold recognition by predicted model quality.
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revision, as accepted by my examiners. I understand that my thesis may be made electronically available to the public. ii Protein structure prediction has been a fundamental challenge in the biological field. In this post-genomic era, the need for automated protein structure prediction has never been more evident and researchers are now focusing on developing computa-tional techniques to predict three-dimensional structures with high throughput. Consensus-based protein structure prediction methods are state-of-the-art in automatic protein structure prediction. A consensus-based server combines the outputs of several individual servers and tends to generate better predictions than any individual server. Consensus-based methods have proved to be successful in recent CASP (Critical Assessment of Structure Prediction). In this thesis, a Support Vector Machine (SVM) regression-based consensus method is proposed for protein fold recognition, a key component for high through-put protein structure prediction and protein function annotation. The SVM first extracts the features of a structural model by comparing the model to the other models produced by all the individual servers. Then, the SVM predicts the quality of each model. The experimental results from several LiveBench data sets confirm that our proposed consensus method, SVM regression, consistently performs better than any individual server. Based on this method, we developed a meta server, the Alignment by Consensus Estimation (ACE). iii
Dynamic Delaunay Triangulation for Wireless Ad Hoc Network.

Gabor Feature Based Classification Using 2D Linear Discriminant Analysis for Face Recognition.

A Statistical Model for Detecting Abnormality in Static%2DPriority Scheduling Networks with Differentiated Services.
Abstract. This paper presents a new statistical model for detecting signs of abnormality in static-priority scheduling networks with differentiated services at connection levels on a class-by-class basis. The formulas in terms of detection probability, miss probability, probabilities of classifications, and detection threshold are proposed.
Spatial and Temporal Analysis for Optical Imaging Data Using CWT and tICA.

A Novel Method of Image Retrieval Based on Combination of Semantic and Visual Features.

PRESTO A Predictive Storage Architecture for Sensor Networks.
We describe PRESTO, a predictive storage architecture for emerging large-scale, hierarchical sensor networks. In contrast to existing techniques, PRESTO is a proxycentric architecture, where tethered proxies balance the need for interactive querying from users with the energy optimization needs of the remote sensors. The main novelty in this work lies in extensive use of predictive techniques that are a natural fit to the correlated behavior of the physical world. PRESTO exploits technology trends in storage to build an architecture that emphasizes archival at remote sensors and intelligent caching at proxies. The system also addresses user needs for querying such sensor networks by exposing a unified, easy to use data abstraction across numerous proxies and remote sensors. 1
Derivations of Error Bound on Recording Traffic Time Series with Long%2DRange Dependence.

A Nonlinear Adaptive Predictive Control Algorithm Based on OFS Model.

A Novel LDA Approach for High%2DDimensional Data.

Palmprint Recognition Based on Unsupervised Subspace Analysis.

PeerWindow An Efficient%2C Heterogeneous%2C and Autonomic Node Collection Protocol.

Performance of Surgical Robots with Automatically Generated Spatial Virtual Fixtures.

A Robust Approach to Sequence Classification.

Semi%2DSupervised Regression with Co%2DTraining.
The traditional setting of supervised learning requires a large amount of labeled training examples in order to achieve good generalization. However, in many practical applications, unlabeled training examples are readily available but labeled ones are fairly expensive to obtain. Therefore, semi-supervised learning has attracted much attention. Previous research on semi-supervised learning mainly focuses on semi-supervised classification. Although regression is almost as important as classification, semi-supervised regression is largely understudied. In particular, although co-training is a main paradigm in semi-supervised learning, few works has been devoted to co-training style semi-supervised regression algorithms. In this paper, a co-training style semi-supervised regression algorithm, i.e. COREG, is proposed. This algorithm uses two regressors each labels the unlabeled data for the other regressor, where the confidence in labeling an unlabeled example is estimated through the amount of reduction in mean square error over the labeled neighborhood of that example. Analysis and experiments show that COREG can effectively exploit unlabeled data to improve regression estimates.
Determining the Topology of Real Algebraic Surfaces.

ExonHunter a comprehensive approach to gene finding.
We present ExonHunter, a new and comprehensive gene finder system that outperforms existing systems, featuring several new ideas and approaches. Our system combines numerous sources of information (genomic sequences, ESTs, and protein databases of related species) with a gene finder based on hidden Markov model in a novel and systematic way. In our framework, various sources of information are expressed as partial probabilistic statements about positions in the sequence and their annotation. We then combine these into the final prediction with a quadratic programming method extending existing methods. Allowing only partial statements is key to our transparent handling of missing information and coping with the heterogeneous character of individual sources of information. As well, we give a new method for modeling length distribution of intergenic regions in hidden Markov models. On a commonly used test set, ExonHunter performs significantly better than ROSETTA, SLAM, or TWINSCAN, and more than two thirds of genes were predicted completely correctly.
Genre Classification via an LZ78%2DBased String Kernel.
We develop the notion of normalized information distance (NID) [7] into a kernel distance suitable for use with a Support Vector Machine classifier, and demonstrate its use for an audio genre classification task. Our classification scheme involves a relatively small number of low-level audio features, is efficient to compute, yet generates an accuracy which compares well with recent works.
Study of the Impact of Hardware Fault on Software Reliability.

A New Algorithm for Pattern Optimization in Protein%2DProtein Interaction Extraction System.

Spatial Motion Constraints for Robot Assisted Suturing Using Virtual Fixtures.

SETRED Self%2Dtraining with Editing.
Self-training is a semi-supervised learning algorithm in which  a learner keeps on labeling unlabeled examples and retraining itself on  an enlarged labeled training set. Since the self-training process may erroneously  label some unlabeled examples, sometimes the learned hypothesis  does not perform well. In this paper, a new algorithm named Setred  is proposed, which utilizes a specific data editing method to identify and  remove the mislabeled examples from the self-labeled data. In detail, in  each iteration of the self-training process, the local cut edge weight statistic  is used to help estimate whether a newly labeled example is reliable  or not, and only the reliable self-labeled examples are used to enlarge  the labeled training set. Experiments show that the introduction of data  editing is beneficial, and the learned hypotheses of Setred outperform  those learned by the standard self-training algorithm.
WGMDS A WSRF%2DCompliant Information Service on Wireless Grids.

An Approach to Image Retrieval Based on Concept Lattices and Rough Set Theory.

Pervasive Computing Engineering Concept

Discovering Sequence%2DStructure Motifs from Protein Segments and Two Applications.
We present a novel method for clustering short protein segments having strong sequencestructure correlations, and demonstrate that these clusters contain useful structural information via two applications. When applied to local tertiary structure prediction, we achieve ~60 % accuracy with a novel dynamic programming algorithm. When applied to secondary structure prediction based on Support Vector Machines, we obtain a ~2 % gain in Q3 performance by incorporating cluster-derived data into training and classification. These encouraging results illustrate the great potential of using conserved local motifs to tackle protein structure predictions and possibly other important problems in biology. 1
Multi%2DInstance Learning Based Web Mining.
In multi-instance learning, the training set comprises labeled bags that are composed of unlabeled instances, and the task is to predict the labels of unseen bags. In this paper, a web mining problem, i.e. web index recommendation, is investigated from a multi-instance view. In detail, each web index page is regarded as a bag, while each of its linked pages is regarded as an instance. A user favoring an index page means that he or she is interested in at least one page linked by the index. Based on the browsing history of the user, recommendation could be provided for unseen index pages. An algorithm named Fretcit-kNN, which employs the Minimal Hausdorff distance between frequent term sets and utilizes both the references and citers of an unseen bag in determining its label, is proposed to solve the problem. Experiments show that in average the recommendation accuracy of Fretcit-kNN is 81.0% with 71.7% recall and 70.9% precision, which is significantly better than the best algorithm that does not consider the specific characteristics of multi-instance learning, whose performance is 76.3% accuracy with 63.4% recall and 66.1% precision.
Discovering patterns to extract protein%2Dprotein interactions from the literature Part II.
doi:10.1093/bioinformatics/bti493
tPatternHunter gapped%2C fast and sensitive translated homology search .

Fair intelligent admission control over resource%2Dfeedback DiffServ network.

FIAC a resource discovery%2Dbased two%2Dlevel admission control for differentiated service networks.

Human%2DMachine Collaborative Systems for Microsurgical Applications.
Abstract. We describe our current progress in developing Human-Machine Collaborative Systems (HMCSs) for microsurgical applications such as vitreo-retinal eye surgery. Three specific problems considered here are (1) developing of systems tools for describing and implementing an HMCS, (2) segmentation of complex tasks into logical components given sensor traces of a human performing the task, and (3) measuring HMCS performance. Our goal is to integrate these into a full microsurgical workstation with the ability to automatically “parse ” traces of user execution into a task model which is then loaded into the execution environment, providing the user with assistance using online recognition of task state. The major contributions of our work to date include an XML task graph modeling framework and execution engine, an algorithm for real-time segmentation of user actions using continuous Hidden Markov Models, and validation techniques for analyzing the performance of HMCSs. 1
Tri%2DTraining Exploiting Unlabeled Data Using Three Classifiers.

Generating Symbolic Interpolants for Scattered Data with Normal Vectors.

Guest Editors%27 foreword.
this paper is based on a model where vertices and edges are replaced with rings and magnetic springs. Like in other spring algorithms, repulsive and attractive forces are defined among rings. After an initial placement, the rings are iteratively moved according to the forces, until a locally stable state is reached. Unlike other spring algorithms, which were developed for undirected graphs only, the magnetic forces introduced in this model control the orientation of the directed edges. For example, a parallel magnetic field causes an acyclic digraph to be drawn with all the edges pointing downward.
Finding Cancer Biomarkers from Mass Spectrometry Data by Decision Lists.

MAC Layer Admission Control and Priority Re%2Dallocation for Handling QoS Guarantees in Non%2Dcooperative Wireless LANs.

2D%2DLDA A statistical linear discriminant analysis for image matrix.
Abstract−Projection-based face recognition has been widely studied during the past two decades. One of the problems is to require a huge storage space to save the face features obtained from training faces. This paper proposes an SVD-based face retrieval system which requires less memory than the PCA, 2DPCA, Fisher, and 2DFisher approaches. The algorithm tested on the famous ORL (AT&amp;T) face database, consisted of 400 112 × 92 gray level face images equally contributed by 40 subjects, achieves 97.5 % recognition rate of retrievals.
Navigating inner space 3%2DD assistance for minimally invasive surgery.
Abstract — Since its inception about three decades ago, modern minimally invasive surgery has made huge advances in both technique and technology. However, the minimally invasive surgeon is still faced with daunting challenges in terms of visualization and hand-eye coordination. At the Center for Computer Integrated Surgical Systems and Technology (CISST) we have been developing a set of techniques for assisting surgeons in navigating and manipulating the three-dimensional space within the human body. In order to develop such systems, a variety of challenging visual tracking, reconstruction and registration problems must be solved. In addition, this information must be tied to methods for assistance that improve surgical accuracy and reliability but allow the surgeon to retain ultimate control of the procedure and do not prolong time in the operating room. In this article, we present two problem areas, eye microsurgery and thoracic minimally invasive surgery, where computational vision can play a role. We then describe methods we have developed to process video images for relevant geometric information, and related control algorithms for providing interactive assistance. Finally, we present results from implemented systems. I.
PathwayFinder Paving the Way Towards Automatic Pathway Extraction.
Automatically mining protein pathway information from the  vast amount of published literature has been an increasing  need from the pharmaceutical industry and biomedical research community. This task has been proved to be a formidable one. Many systems have been implemented, but  few are practical. Some are too restricted and some are overly ambitious. This paper
Fractional Gaussian Noise A Tool of Characterizing Traffic for Detection Purpose.

Normalizing Traffic Pattern with Anonymity for Mission Critical Applications.

On the k%2DClosest Substring and k%2DConsensus Pattern Problems.
Given a set S =  {s1,s  2,...,s n} of strings each of length m,  and an integer L, we study the following two problems.
Optimizing Multiple Spaced Seeds for Homology Search.
Abstract. Optimized spaced seeds improve sensitivity and specificity in localhomology search [1]. Recently, several authors [2-4] have shown that multiple seeds can have better sensitivity and specificity than single seeds. We describea linear programming-based algorithm to optimize a set of seeds. Our algorithm offers a performance guarantee: the sensitivity of a chosen seed set is at least 70%of what can be achieved, in most reasonable models of homologous sequences. Our method achieves performance comparable to that of a greedy algorithm, butour work gives this area a mathematical foundation.
Finding Cancer Biomarkers from Mass Spectrometry Data by Decision Lists.

Gemini Probabilistic Routing Algorithm in Structured P2P Overlay.

Rational Quadratic Approximation to Real Plane Algebraic Curves.

A Hybrid Hardware%2DAccelerated Algorithm for High Quality Rendering of Visual Hulls.
In this paper, a novel hybrid algorithm is presented for the fast construction and high-quality rendering of visual hulls. We combine the strengths of two complementary hardware-accelerated approaches: direct constructive solid geometry (CSG) rendering and texture mapping-based visual cone trimming. The former approach completely eliminates the aliasing artifacts inherent in the latter, whereas the rapid speed of the latter approach compensates for the performance deficiency of the former. Additionally, a new view-dependent texture mapping method is proposed. This method makes efficient use of graphics hardware to perform per-fragment blending weight computation, which yields better rendering quality. Our rendering algorithm is integrated in a distributed system that is capable of acquiring synchronized video streams and rendering visual hulls in real time or at interactive frame rates from up to eight reference views.
Spatial Motion Constraints in Medical Robot using Virtual Fixtures Generated by Anatomy.
Abstract- In Ear, Nose and Throat (ENT) surgery, the operating volume is very limited. This is especially true in sinus surgery, when the instrument passes through the nasal and sinus cavity to reach the pathological area. The nasal and sinus bones impose geometric constraints on the work volume. During the surgery, the surgeon needs to control the motion of the instrument tip to accomplish some delicate procedure; meanwhile he/she needs to avoid hitting anatomic constraints. In this paper, we present a method to assist the path following task in a constrained area. The system reads the user’s force input and combines it with the planned tip-trajectory to create the tip motion constraints; meanwhile it generates the tool-shaft boundary constraints based on a 3-D geometric model. We map instrument tip motion and boundary information to joint displacements via robot kinematics, and then use a constrained quadratic optimization algorithm to compute the optimal set of corresponding joint displacements. In the preliminary study, we show that robot guidance using cooperative control and virtual fixtures derived from complex geometry can assist users in skilled manipulation tasks, while maintaining desirable properties such as collision avoidance and safety. Index Terms- collaborative manipulation; virtual fixture; optimization robot control; geometry constraint. I.
SmartBoa Constructing p2p Overlay Network in the Heterogeneous Internet Using Irregular Routing Tables.

Practical Byzantine Fault Tolerance Using Fewer than 3f 1 Active Replicas.

Improving Melody Classification by Discriminant Feature Extraction and Fusion.

Validation of a Methodology for Assessing Software Reliability.

Twins 2%2Dhop Structured Overlay with High Scalability.

Scale%2DInvariant Registration of Monocular Endoscopic Images to CT%2DScans for Sinus Surgery.
In this paper, we present a novel method for intra-operative registration directly from monocular endoscopic images. This technique has the potential to provide a more accurate surface registration at the surgical site than existing methods. It can operate autonomously from as few as two images and can be particularly useful in revision cases where surgical landmarks may be absent. A by-product of video registration is an estimate of the local surface structure of the anatomy, thus providing the opportunity to dynamically update anatomical models as the surgery progresses. Our approach is based on a previously presented method [12] for reconstruction of a scaled 3D model of the environment from unknown camera motion. We use this scaled reconstruction as input to a PCA-based algorithm that registers the reconstructed data to the CT data and recovers the scale and pose parameters of the camera in the coordinate frame of the CT scan. The result is used in an ICP registration step to refine the registration estimates. The details of our approach and the experimental results with a phantom of a human skull and a head of a pig cadaver are presented in this paper. Key words: image registration, monocular reconstruction, vision-based SLAM, Sinus surgery
Design and Implementation of a Large%2DScale Context Fusion Network.
In this paper we motivate a Context Fusion Network (CFN), an infrastructure model that allows contextaware applications to select distributed data sources and compose them with customized data-fusion operators into a directed acyclic information fusion graph. Such a graph represents how an application computes high-level understandings of its execution context from low-level sensory data. Multiple graphs by different applications inter-connect with each other to form a global graph. A key advantage of a CFN is re-usability, both at code-level and instance-level, facilitated by operator composition. We designed and implemented a distributed CFN system, Solar, which maps the logical operator graph representation onto a set of overlay hosts. In particular, Solar meets the challenges inherent to heterogeneous and volatile ubicomp environments. By abstracting most complexities into the infrastructure, Solar facilitates both the development and deployment of context-aware applications. We present the operator composition model, basic services of the Solar overlay network, and programming support for the developers. We also discuss some applications built with Solar and the lessons we learned from our experience. 1
Adaptive Portal Aggregation for Pervasive Client Devices.

An Empirical Autocorrelation Form for Modeling LRD Traffic Series.

Statistical Error Analysis on Recording LRD Traffic Time Series.

A Method to Obtain Signatures from Honeypots Data.

Probability Principle of a Reliable Approach to Detect Signs of DDOS Flood Attacks.

ONSP Parallel Overlay Network Simulation Platform.
Abstract. In research of overlay networks, simulator takes a very important role. However, popular simulators, such as ns and PlanetLab can’t meet the scale and performance requirement of overlay research. Although it is necessary for overlay researchers to observe activities of million nodes, current simulators can not give such simulation result. To improve the overlay network research efficiency, we design and implement ONSP, a novel parallel overlay network simulation platform, which provides parallel discrete event simulation of overlay networks on high performance cluster. With this tool, we are able to build overlay network simulator in large scale easily and test it in short time. The test result proves that ONSP can well address the requirement of performance and scalability. overlay network, discrete event simulation, parallel 1.
End%2Dto%2DEnd Framework for QoS Guarantee in Heterogeneous Wired%2Dcum%2DWireless Networks.

Discovering patterns to extract protein%2Dprotein interactions from full texts.
  Motivation: Although there are several databases storing protein–protein interactions, most such data still exist only in the scientific literature. They are scattered in scientific literature written in natural languages, defying data mining efforts. Much time and labor have to be spent on extracting protein pathways from literature. Our aim is to develop a robust and powerful methodology to mine protein–protein interactions from biomedical texts. Results: We present a novel and robust approach for extracting protein–protein interactions from literature. Our method uses a dynamic programming algorithm to compute distinguishing patterns by aligning relevant sentences and key verbs that describe protein interactions. A matching algorithm is designed to extract the interactions between proteins. Equipped only with a dictionary of protein names, our system achieves a recall rate of 80.0 % and precision rate of 80.5%.
Hardware%2DAccelerated Rendering of Photo Hulls.
This paper presents an efficient hardware-accelerated method for novel view synthesis from a set of images or videos. Our method is based on the photo hull representation, which is the maximal photo-consistent shape. We avoid the explicit reconstruction of photo hulls by adopting a view-dependent plane-sweeping strategy. From the target viewpoint slicing planes are rendered with reference views projected onto them. Graphics hardware is exploited to verify the photo-consistency of each rasterized fragment. Visibilities with respect to reference views are properly modeled, and only photo-consistent fragments are kept and colored in the target view. We present experiments with real images and animation sequences. Thanks to the more accurate shape of the photo hull representation, our method generates more realistic rendering results than methods based on visual hulls. Currently, we achieve rendering frame rates of 2-3 fps. Compared to a pure software implementation, the performance of our hardware-accelerated method is approximately 7 times faster.
Rational quadratic approximation to real algebraic curves.
www.elsevier.com/locate/cagd An algorithm is proposed to give a global approximation of an implicit real plane algebraic curve with rational quadratic B-spline curves. The algorithm consists of four steps: topology determination, curve segmentation, segment approximation and curve tracing. Due to the detailed geometric analysis, high accuracy of approximation may be achieved with a small number of quadratic segments. The final approximation keeps many important geometric features of the original curve such as the topology, convexity and sharp points. Our method is implemented and experiments show that it may achieve better approximation bound with less segments than previously known methods. We also extend the method to approximate spatial algebraic curves.
An approach to reliably identifying signs of DDOS flood attacks based on LRD traffic pattern recognition.
Abstract:- Information integrity of communication data is crucial to e-business systems. An adversary may delete or insert packets into a normal communication data series in e-business systems to destroy information integrity to produce deserters (likely informal, this paper uses the term tamped type attacks to specifically describe those that attackers detect or insert packets into a normal data series). Consequently, a security issue in an e-business system is how to detect tamped type attacks. From a view of intrusion detection systems, statistic methods of intrusion detection are increasingly paid attention to [1-3]. This short paper gives a method for statistically real-time detection of tampered type attacks. The method is based on power spectra of monitored traffic time series with finite length. The detection probability is derived. A case study is demonstrated with a real-traffic series to suggest that the present method can be used to give an alarm at the early stage of intrusions. Key-Words:- Network-based IDS, anomaly intrusion detection, information integrity, pattern matching 1
On spaced seeds for similarity search.
Genomics studies routinely depend on similarity searches based on the  strategy of finding short seed matches (contiguous k bases) which are then  extended. The particular choice of the seed length, k, is determined by the  tradeoff between search speed (larger k reduces chance hits) and sensitivity  (smaller k finds weaker similarities). A novel idea of using a single  deterministic optimized spaced seed was introduced in [10] to the above  similarity search process and it was empirically demonstrated that the optimal  spaced seed quadruples the search speed, without sacrificing sensitivity.
The similarity metric.
A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new &#034;normalized information distance&#034;, based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric. This theory forms the foundation for a new practical tool. To evidence generality and robustness we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.
Shared information and program plagiarism detection.
A fundamental question in information theory and in computer science is how to measure similarity  or the amount of shared information between two sequences. We have proposed a metric, based on Kolmogorov  complexity to answer this question, and have proven it to be universal. We apply this metric in  measuring the amount of shared information between two computer programs, to enable plagiarism detection. We have
Optimal synchronous coding.
We consider the problem of constructing statistically synchronizable codes over  arbitrary alphabets and for any finite source. We show how to efficiently construct a  statistically synchronizable code whose average codeword length is whithin the least  likely codeword probability from that of the Huffman code for the same source.  Moreover, we give a method for constructing codes having a synchronizing codeword.  The codes we construct present high synchronizing capability and low redundancy.  3  Part of this work was done while visiting IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York, 10598.  This work was partially supported by the Italian Ministry of the University and Scientific Research, within the framework of the Project: Progetto ed Analisi di Algoritmi. Part of this work has been presented at the 1990 IEEE International Symposium on Information Theory, San Diego, CA, Jan. 1990. 1  1 Introduction  A basic problem in information transmission is to mai...
Selecting the branches for an evolutionary tree. A polynomial time approximation scheme.

Patternhunter Ii Highly Sensitive and Fast Homology Search.
Extending the single optimized spaced seed of PatternHunter [20] to multiple ones, PatternHunter  II simultaneously remedies the lack of sensitivity of Blastn and the lack of speed of SmithWaterman,  for homology search. At Blastn speed, PatternHunter II approaches Smith-Waterman  sensitivity, bringing homology search technology back to a full circle.
A Tutorial of Recent Developments in the Seeding of Local Alignment.
We review recent results on local alignment. We begin with a review of classical methods and early heuristic methods, and then focus on more recent work on the seeding of local alignment. We show that these techniques give a vast improvement in both sensitivity and specificity over previous methods, and can achieve sensitivity at the level of classical algorithms while requiring orders of magnitude less runtime.
Protein Threading by Linear Programming Theoretical Analysis and Computational Results.

A Note on the Single Genotype Resolution Problem.

Mechanism for convex corner undercutting of %28110%29 silicon in KOH.

A Learning Algorithm of CMAC Based on RLS.

Index Selection for Efficient XML Path Expression Processing.

Improvement of Routing Structure in P2P Overlay Networks.

Hardware%2DAccelerated Visual Hull Reconstruction and Rendering.
We present a novel algorithm for simultaneous visual hull reconstruction and rendering by exploiting off-the-shelf graphics hardware. The reconstruction is accomplished by projective texture mapping in conjunction with the alpha test. Parallel to the reconstruction, rendering is also carried out in the graphics pipeline. We texture the visual hull view-dependently with the aid of fragment shaders, such as nVIDIA&#039;s register combiners. Both reconstruction and rendering are done in a single rendering pass. We achieve frame rates of more than 80 fps on a standard PC equipped with a commodity graphics card. The performance is significantly faster than that of previously reported similar systems.
Recognition of Operator Motions for Real%2DTime Assistance Using Virtual Fixtures.
Hidden Markov Models (HMMs) are used for automatic segmentation and recognition of user motions. A new algorithm for real-time HMM recognition was developed. The segmentation results are used to provide appropriate assistance in a combined curve following and object avoidance task. This assistance takes the form of a virtual fixture, whose compliance can be altered online. Recognition and assistance experiments were performed using force and position data recorded from a cooperative manipulation system, where a robot and a human operator hold an instrument simultaneously. Recognition accuracy exceeds 90%, even when the users training the HMMs differ from those executing the task. For a task consisting of both path following and avoidance motions, an HMM-based virtual fixture switches the compliance from low to high when the user is trying to move away from the path. The HMM method improves operator performance in comparison with a constant virtual fixture and no virtual fixture.
Class%2DBased Fair Intelligent Admission Control over an Enhanced Differentiated Service Network.

Spatial motion constraints theory and demonstrations for robot guidance using virtual fixtures.
In this article, we describe and demonstrate control algorithms for general motion constraints. These constraints are designed to enhance the accuracy and speed of a user manipulating in an environment with the assistance of a cooperative or telerobotic system. Our method uses a basis of preferred directions, created off-line or in real-time using sensor data, to generate virtual fixtures that may constrain the user to a curve, surface, orientation, etc. in space. Open loop virtual fixtures seek only to maintain user motion along preferred directions, whereas closed loop fixtures additionally guide the user toward a point, line, or surface. This article demonstrates and compares the effects of open and closed loop fixtures in both autonomous and humanmachine cases.
Human%2DMachine Collaborative Systems for Microsurgical Applications.
Abstract. We describe our current progress in developing Human-Machine Collaborative Systems (HMCSs) for microsurgical applications such as vitreo-retinal eye surgery. Three specific problems considered here are (1) developing of systems tools for describing and implementing an HMCS, (2) segmentation of complex tasks into logical components given sensor traces of a human performing the task, and (3) measuring HMCS performance. Our goal is to integrate these into a full microsurgical workstation with the ability to automatically “parse ” traces of user execution into a task model which is then loaded into the execution environment, providing the user with assistance using online recognition of task state. The major contributions of our work to date include an XML task graph modeling framework and execution engine, an algorithm for real-time segmentation of user actions using continuous Hidden Markov Models, and validation techniques for analyzing the performance of HMCSs. 1
Integrating Software into PRA.

Abstract Analysis of Detection Probability for Statistically Detecting DDoS Attacks.

Optimum Robot Control for 3D Virtual Fixture in Constrained ENT Surgery.

On flow reservation and admission control for distributed scheduling strategies in IEEE802.11 wireless LAN.
Providing service differentiation in IEEE802.11 Wireless LANs [3] has been investigated by many researchers ([2], [5], [6], [7], [9], [13]). It has been shown [1] that some distributed schedulers such as DFS [9] and EDCF [5] can achieve high throughput and certain service differentiation comparing to DCF and PCF provided that the traffic load in the system is low or medium. However, those strategies do not support flow reservation and thus cannot guarantee QoS requirements of high priority real-time flows under overloading network traffics. In this paper, we present a MAC layer flow reservation and admission control scheme for distributed scheduling strategies in the aim of achieving QoS guarantee in IEEE802.11 wireless LANs. Our approach has several desirable features: (1) It can work with most of the distributed scheduling strategies like DCF, DFS, EDCF without modification of the underlying scheduling mechanism. (2) A dynamic priority re-allocation method is integrated with the admission control to further improve system throughput. (3) Misuse of priority can be easily handled. Simulation of our proposed reservation scheme upon various distributed scheduling strategies has been conducted, and results show that this scheme can achieve low collision rate, high throughput, and less delay.
Protein Threading by Linear Programming.
this paper investigates the effectiveness of a new method: protein threading  via linear programming. Based on the contact map model of protein 3D structure   we formulate the protein threading problem as a large scale integer programming  problem then relax to a linear programming problem and finally solve the  integer program by a branch-and-bound method. The final solution is optimal with  respect to energy functions incorporating pairwise interaction and allowing variable  gaps. The algorithm has been implemented as software package RAPTOR - RApid  Protein Threading predictOR. Experimental results for fold recognition show that  RAPTOR significantly outperforms other programs at the fold similarity level. The  RAPTOR webserver is at http://www.cs.uwaterloo.ca/~j3xu/RAPTORorm.htm  I 
Achieving Flow Fairness in DiffServ Class Per%2Dflow Fair Admission Control over Differentiated Service Network.

The similarity metric.
A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new &#034;normalized information distance&#034;, based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric. This theory forms the foundation for a new practical tool. To evidence generality and robustness we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.
Improved Hardware%2DAccelerated Visual Hull Rendering.
The visual hull is an efficient shape approximation for the purpose of reconstructing and visualizing dynamic objects. Recently, rapid progress in graphics hardware development has made it possible to render visual hulls from a set of silhouette images in real-time.
A Flexible and Versatile Studio for SynchronizedMulti%2DView Video Recording.
In recent years, the convergence of computer vision and computer graphics has put forth new research areas  that work on scene reconstruction from and analysis of multi-view video footage. In free-viewpoint video, for  example, new views of a scene are generated from an arbitrary viewpoint in real-time using a set of multi-view  video streams as inputs. The analysis of real-world scenes from multi-view video to extract motion information  or reflection models is another field of research that greatly benefits from high-quality input data. Building a  recording setup for multi-view video involves a great effort on the hardware as well as the software side. The  amount of image data to be processed is huge, a decent lighting and camera setup is essential for a naturalistic  scene appearance and robust background subtraction, and the computing infrastructure has to enable real-time  processing of the recorded material. This paper describes our recording setup for multi-view video acquisition that  enables the synchronized recording of dynamic scenes from multiple camera positions under controlled conditions.
Online Accelerated Rendering of Visual Hulls in Real Scenes.
This paper presents an online system which is capable of reconstructing and rendering dynamic objects in real scenes. We reconstruct visual hulls of the objects by using a shape-from-silhouette approach. During rendering, a novel blending scheme is employed to compose multiple background images. Visibility artifacts on the dynamic object are removed by using opaque projective texture mapping. We also propose a dynamic texture packing technique to improve rendering performance by exploiting region-of-interest information. Our system takes multiple live or pre-recorded video streams as input. It produces realistic real-time rendering results of dynamic objects in their surrounding natural environment in which the user can freely navigate.
MOLVIE an interactive visualization environment for molecular structures.

A Ranking of Software Engineering Measures Based on Expert Opinion.

Distinguishing string selection problems.
This paper presents a collection of string algorithms that are at the core of several biological problems such as discovering potential drug targets, creating diagnostic probes, universal primers or unbiased consensus sequences. All these problems reduce to the task of finding a pattern that, with some error, occurs in one set of strings (Closest Substring Problem) and does not occur in another set (Farthest String Problem). In this paper, we break down the problem into several subproblems and prove the following results. 1. The following are all NP-Hard: the Farthest String Problem, the Closest Substring Problem, and the Closest String Problem of finding a string that is close to each string in a set. 2. There is a PTAS for the Farthest � String � Problem based on a linear programming relaxation technique. 43 3. There is a polynomial-time + ɛ-approximation algorithm for the Closest String Problem for any small constant ɛ&gt;0. Using this algorithm, we also provide an efficient heuristic algorithm for the Closest Substring Problem. 4. The problem of finding a string that is at least Hamming distance d from as many strings in a set as possible,
Sharpening Occam%27s razor.
this paper) then better &#034;i# Occam style&#034; characterizations of polynomial time learnability/predicatability can be given. They rely on Schapire&#039;s result that &#034;weak learnability&#034; equals &#034;strong learnability&#034; in polynomial time [13] exploited in [9]. For a recent survey of the important related &#034;boosting&#034; technique see [14]
Sharpening Occam%27s razor.
this paper) then better &#034;i# Occam style&#034; characterizations of polynomial time learnability/predicatability can be given. They rely on Schapire&#039;s result that &#034;weak learnability&#034; equals &#034;strong learnability&#034; in polynomial time [13] exploited in [9]. For a recent survey of the important related &#034;boosting&#034; technique see [14]
Optimal Prefix Codes and Huffman Codes.
. Given an alphabet \Sigma = fa1 ; : : : ; ang with a corresponding  list of positive weights fw1 ; : : : ; wng and a length restriction L, the  length-restricted prefix code problem is to find, a prefix code that minimizes  P n  i=1 w i l i , where l i , the length of the codeword assigned to a i ,  cannot be greater than L, for i = 1; : : : ; n. In this paper, we present an  efficient implementation of the WARM-UP algorithm, an approximative  method for this problem. The worst-case time complexity of WARM-UP  is O(n log n +n log wn ), where wn is the greatest weight. However, some  experiments with a previous implementation of WARM-UP show that  it runs in linear time for several practical cases, if the input weights are  already sorted. In addition, it often produces optimal codes. The proposed  implementation combines two new enhancements to reduce the  space usage of WARM-UP and to improve its execution time. As a result,  it is about ten times faster than the previous implementat...
Decision Analysis of Statistically Detecting Distributed Denial%2Dof%2DService Flooding Attacks.

Raptor Optimal Protein Threading by Linear Programming.
This paper presents a novel linear programming approach to do protein 3-dimensional (3D) structure  prediction via threading. Based on the contact map graph of the protein 3D structure template, the  protein threading problem is formulated as a large scale integer programming (IP) problem. The IP  formulation is then relaxed to a linear programming (LP) problem, and then solved by the canonical  branch-and-bound method. The final solution is globally optimal with respect to energy functions. In  particular, our energy function includes pairwise interaction preferences and allowing variable gaps  which are two key factors in making the protein threading problem NP-hard. A surprising result is  that, most of time, the relaxed linear programs generate integral solutions directly. Our algorithm has  been implemented as a software package RAPTOR -- RApid Protein Threading by Operation Research  technique. Large scale benchmark test for fold recognition shows that RAPTOR significantly  outperforms other programs at the fold similarity level. The CAFASP3 evaluation, a blind and public  test by the protein structure prediction community, ranks RAPTOR as top 1, among individual prediction  servers, in terms of the recognition capability and alignment accuracy for Fold Recognition  (FR) family targets. RAPTOR also performs very well in recognizing the hard Homology Modeling  (HM) targets. RAPTOR was implemented at the University of Waterloo and it can be accessed at  http://www.cs.uwaterloo.ca/j3xu/RAPTOR form.htm
Design and Validation of Portable Communication Infrastructure for Fault%2DTolerant Cluster Middleware.
We describe the communication infrastructure (CI) for our fault-tolerant cluster middleware, which is optimized for two classes of communication: for the applications and for the cluster management middleware. This CI was designed for portability and for efficient operation on top of modern user-level message passing mechanisms. We present a functional fault model for the CI and show how platform-specific faults map to this fault model. Based on this fault model, we have developed a fault injection scheme that is integrated with the CI and is thus portable across different communication technologies. We have used fault injection to validate and evaluate the implementation of the CI itself as well as the cluster management middleware in the presence of communication faults.
Sharpening Occam%27s Razor.
this paper) then better &#034;i# Occam style&#034; characterizations of polynomial time learnability/predicatability can be given. They rely on Schapire&#039;s result that &#034;weak learnability&#034; equals &#034;strong learnability&#034; in polynomial time [13] exploited in [9]. For a recent survey of the important related &#034;boosting&#034; technique see [14]
Construct Piecewise Hermite Interpolation Surface with Blending Methods.
Three methods are proposed to construct a piecewise Hermite interpolation surface (PHIS), which is a piecewise algebraic surface interpolating a set of given points with associated normal directions. The surface is obtained by blending together some low-degree surface patches. Both the first and the second methods are completely local and give a surface with G n-continuity. In the third construction, we reduce the number of surfaces patches by joining as many cubic patches as possible.This method gives a global solution with G 1-continuity. These three different methods can be used to meet different requirements of the designers.
Combining stereo and visual hull information for on%2Dline reconstruction and rendering of dynamic scenes.
In this paper, we present a novel system which combines depth from stereo and visual hull reconstruction for acquiring dynamic real-world scenes at interactive rates. First, we use the silhouettes from multiple views to construct a polyhedral visual hull as an initial estimation of the object in the scene. The visual hull is used to limit the disparity range during stereo estimation. The use of the constraints imposed by the silhouettes from the earlier processing stage reduces the amount of computation significantly. The restricted search range improves both the speed and the quality of the stereo reconstruction. In return, stereo information can compensate for some of the inherent drawbacks of the visual hull method, such as inability to reconstruct some concave regions.
Fair Intelligent Congestion Control Resource Discovery Protocol on TCP based Network.
Abstract Today’s Internet only provides best-effort service for all traffics. The network is not able to guarantee the quality of service required by an application that demands more stringent response in terms of delay, jitters, bandwidth and etc. It is well accepted that, the deployment of QoS-aware technologies is a key factor for the continued success of the Internet. In this paper, we propose a Fair Intelligent Congestion Control Resource Discovery (FICCRD) protocol on TCP based network whereby a mechanism is employed at core routers to determine available network resources and convey this information to edge routers. At the edge routers, an intelligent control algorithm is employed to assist the TCP to maximize its traffic over the underlying network. The key ideas are to integrate available network resources in estimating connections ’ fair share; to create feedback control loops between edge routers; to employ a special Resource Discovery (RD) packet to collect and convey en route router state information; and to employ intelligent algorithms to match a TCP connection’s sending rate to the rate at which the underlying network can support. We demonstrate that FICCRD protocol is effective, fair, flexible and can be easily extended for QoS control of the future Internet.
Fair Intelligent Feedback Mechanism on TCP Based Network.

On Synchronous Coding.
In code-division multiple-access systems, simultaneous mul-tiuser accessing of a common channel is made possible by assigning a signature waveform to each user. Knowledge of these waveforms enables the receiver to demodulate the data streams of each user, upon observation of the sum of the transmitted signals, perturbed by additive noise. Under the assumptions of symbol-synchronous transmissions and white Gaussian noise, we analyze the detection mechanism at the receiver, comparing different detectors by their bit error rate in the low background noise region, and by their worst-case behavior in a near-far environment where the received energies of the users are not necessarily similar. Optimum multiuser detection achieves important performance gains over conven-tional single-user detection at the expense of computational complexity that grows exponentially with the number of users. It is shown that in the synchronous case the performance achieved by linear multiuser detectors (whose complexity per demodulated bit is only linear in the number of users) is similar to that of optimum multiuser detection. Attention is focused on detectors whose linear memoryless transformation is a general-ized inverse of the matrix of signature waveform crosscorrelations, and on the optimum linear detector. It is shown that the generalized inverse detectors exhibit the same degree of near-far resistance as the optimum multiuser detector; the optimum linear detector is obtained subsequently, along with sufficient conditions on the signal energies and crosscorrelations to ensure that its performance is equal to that of the optimum multiuser detector.
Fair Intelligent Feedback Mechanism on TCP Based Network.

DNACompress fast and effective DNA sequence compression.

PatternHunter faster and more sensitive homology search.
Motivation: Genomics and proteomics studies routinely depend on homology searches based on the strategy of finding short seed matches which are then extended. The exploding genomic data growth presents a dilemma for DNA homology search techniques: increasing seed size decreases sensitivity whereas decreasing seed size slows down computation. Results: We present a new homology search algorithm &#034;PatternHunter&#034; that uses a novel seed model for increased sensitivity and new hit-processing techniques for significantly increased speed. At Blast levels of sensitivity, PatternHunter is able to find homologies between sequences as large as human chromosomes, in mere hours on a desktop. Availability: PatternHunter is available at
Sharpening Occam%27s Razor
this paper) then better &#034;i# Occam style&#034; characterizations of polynomial time learnability/predicatability can be given. They rely on Schapire&#039;s result that &#034;weak learnability&#034; equals &#034;strong learnability&#034; in polynomial time [13] exploited in [9]. For a recent survey of the important related &#034;boosting&#034; technique see [14]
Fuzzy Adaptive Control of Nonlinear Processes with Feedforward Compensator and its Application.

An approach to discrete%2Dtime incentive feedback Stackelberg games.
Abstract—A substantial effort has been devoted to various incentive Stackelberg solution concepts. Most of these concepts work well in the sense that the leader can get his desired solution in the end. Yet, most incentive strategies developed thus far include either the follower’s control, which may not be realistic in practice, or delays in the state, which makes stabilization more difficult to achieve. In this paper, we obtain the team-optimal state feedback Stackelberg strategy (with no delays) of an important class of discrete-time two-person nonzero-sum dynamic games characterized by linear state dynamics and quadratic cost functionals. Index Terms—Games, incentive, Stackelberg, stability, team-optimal. I.
Improving Chinese Storing Text Retrieval Systems%27 Security via a Novel Maximal Prefix Coding.
As we have seen that Huffman coding has been widely used in data, image, and video compression. In this paper novel maximal prefix coding is introduced. Relationship between the Huffman coding and the optimal maximal prefix coding are discussed. We show that all Huffman coding schemes are optimal maximal prefix coding schemes and that conversely the optimal maximal prefix coding schemes need not to be the Huffman coding schemes. Moreover, it is proven that, for any maximal prefix code C, there exists an information source I = (, P) such that C is exactly a Huffman code for I. Therefore, it is essential to show that the class of Huffman codes is coincident with one of maximal prefix codes. A case study of data compression is also given. Comparing the Huffman coding, the maximal prefix coding is used for not only statistical modeling but also dictionary methods. And it is good at applying to a large information retrieval system and improving its security.
On the closest string and substring problems.
The problem of finding a center string that is `close&#039; to every given string arises in computational molecular biology and coding theory. This problem has two versions: the Closest String problem and the Closest Substring problem. Given a set of strings  S = fs 1 ; s 2 ; : : : ; s n g, each of length m, the Closest String problem is to find the smallest  d and a string s of length m which is within Hamming distance d to each s i 2 S. This problem comes from coding theory when we are looking for a code not too far away from a given set of codes. Closest Substring problem, with an additional input integer L, asks for the smallest d and a string s, of length L, which is within Hamming distance d away from a substring, of length L, of each s i . This problem is much more elusive than the Closest String problem. The Closest Substring problem is formulated from applications in finding conserved regions, identifying genetic drug targets and generating genetic probes in molecular biology. Whether there are efficient approximation algorithms for both problems are major open questions in this area. We present two polynomial time approximation algorithms with approximation ratio 1 + ffl for any small ffl to settle both questions.
Finding Similar Regions in Many Sequences.
Algorithms for finding similar, or highly conserved, regions in a group of sequences  are at the core of many molecular biology problems. Assume that we are given n DNA  sequences s 1 ; : : : ; s n . The Consensus Patterns problem, which has been widely studied  in bioinformatics research [22, 10, 7, 21, 2, 3, 9, 18, 19, 27], in its simplest form, asks  for a region of length L in each s i , and a median string s of length L so that the total  Hamming distance from s to these regions is minimized. We show that the problem is  NP-hard and give a polynomial time approximation scheme (PTAS) for it. We then  present an efficient approximation algorithm for the consensus pattern problem under  the original relative entropy measure of [22, 10, 7, 21]. As an interesting application  of our analysis, we further obtain a PTAS for a restricted (but still NP-hard) version  of the important consensus alignment problem [6] allowing at most constant number of  gaps, each of arbitrary length, in each sequence.
Foreword.
reference set of international guidelines and recommendations for the reporting and presentation of statistical data and metadata. Although, the Handbook was prepared primarily for short-term economic statistics, many, if not most of the recommendations presented are also relevant for annual (structural) statistics and for social and population statistics. The Handbook draws heavily on existing international statistical guidelines and recommendations that have been developed over the last twenty years by international organisations and national statistical agencies. These international standards have been developed for implementation by international organisations themselves and by national agencies in both developed and developing economies. The need for the articulation of a comprehensive set of recommendations on the reporting and presentation of statistical data and metadata is one aspect of the overall demand for improved international comparability and consistency of statistics compiled and published by national agencies and international organisations. This requirement has itself been driven by closer economic and social linkages between both the 30 OECD Member countries and between those countries and large emerging non-member economies. As discussed in the Handbook, the major causes of differences in statistics compiled in different countries flow from the use of different definitions and concepts and
The average%2Dcase area of Heilbronn%2Dtype triangles.
 From among �  � n triangles with vertices chosen from n points in the unit square, 3 let T be the one with the smallest area, and let A be the area of T. Heilbronn’s triangle problem asks for the maximum value assumed by A over all choices of n points. We consider the average-case: If the n points are chosen independently and at random (with a uniform distribution), then there exist positive constants c and C such that c/n3 &lt;µ n &lt; C/n3 for all large enough values of n, where µ n is the expectation of A. Moreover, c/n3 &lt;A&lt;C/n3, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in
Nonlinear System Input Structure Identification Based on Rough Set Data Analysis.

An information%2Dbased sequence distance and its application to whole mitochondrial genome phylogeny.

A New Approach to Formal Language Theory by Kolmogorov Complexity
We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for regular languages, and a new method to separate deterministic context-free languages and nondeterministic context-free languages. The use of the new `incompressibility arguments&#039; is illustrated by many examples. The approach is also successful at the high end of the Chomsky hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov complexity. (This is a preliminary uncorrected version. The final version is the one published in SIAM J. Comput., 24:2(1995), 398-410.) 1 Introduction  It is feasible to reconstruct parts of formal language theory using algorithmic information theory (Kolmogorov complexity). We provide theorems on how to use Kolmogorov complexity as a concrete and powerful tool. We do not just want    A preliminary version of part of this work was presented at the 16th International...
The similarity metric
A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new &#034;normalized information distance&#034;, based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the similarity metric. This theory forms the foundation for a new practical tool. To evidence generality and robustness we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.
On%2Dthe%2DFly Processing of Generalized Lumigraphs.
We introduce a flexible and powerful concept for reconstructing arbitrary views from multiple source images on the fly. Our approach is based on a Lumigraph structure with per-pixel depth values, and generalizes the classical two-plane parameterized light fields and Lumigraphs. With our technique, it is possible to render arbitrary views of time-varying, non-diffuse scenes at interactive frame rates, and it allows using any kind of sensor that yields images with dense depth information. We demonstrate the flexibility and efficiency of our approach through various examples.
Hybrid Evolutionary Search Method Based on Clusters.


A Compact Fourth%2DOrder Finite Difference Scheme for Unsteady Viscous Incompressible Flows.


The Incompressibility Method.
. We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are: (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency (how far it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.  Key words. Kolmogorov complexity, incompressiblity method, random graphs, enumeration of graphs, algorithmic information theory  AMS subject classifications. 68Q30, 05C80, 05C35, 05C30  1. Introduction. The incompressibility of individual random objects yields a simple but powerful proof technique. The incompressibility method, [9], is a new general purpose tool and should be compared with the pigeon hole principle or the probabilistic method. Here we apply the incompressibility metho...
Selected papers from ALT 1997 %2D Foreword.

Ranking Software Engineering Measures Related to Reliability Using Expert Opinion.

A compression algorithm for DNA sequences and its applications in genome comparison.
We present a lossless compression algorithm, GenCompress, for genetic sequences, based on searching for approximate repeats. Our algorithm achieves the best compression ratios for benchmark DNA sequences. Significantly better compression results show that the approximate repeats are one of the main hidden regularities in DNA sequences. We then describe a theory of measuring the relatedness between two DNA sequences. Using our algorithm, we present strong experimental support for this theory, and demonstrate its application in comparing genomes and constructing evolutionary trees. 1
Computing the quartet distance between evolutionary trees.
The comparison of evolutionary trees is a fundamental problem in evolutionary biology. Di erent evolutionary hypotheses (or con icting phylogenies) arise
A practical algorithm for recovering the best supported edges of an evolutionary tree %28extended abstract%29.
)  Vincent Berry  David Bryant  y  Tao Jiang  z  Paul Kearney  x  Ming Li  --  Todd Wareham  k  Haoyong Zhang  Abstract  It is now routine for biologists to conduct evolutionary analyses of large DNA and protein sequence datasets. A computational bottleneck in these analyses is the recovery of the topology of the evolutionary tree for a set of sequences. This paper presents a practical solution to this challenging problem. In particular, a new technique, called hypercleaning, is presented that can be combined with various tree-building algorithms to efficiently reconstruct from sequence data the best supported edges of the evolutionary tree. More precisely, the hypercleaning technique computes from sequence data a small subset of edges that is likely to contain most edges of the correct Address: D&#039;epartement d&#039;Informatique Fondamentale et Applications, LIRMM, Universit&#039;e de Montpellier II, France. Part of this work was done at the D&#039;epartement de Math&#039;ematiques,EURISE, Universit&#039;e de S...
Estimating DNA sequence entropy.
Abstract This paper presents the first entropy estimator for DNA sequences that has both proven properties and excellent entropy estimates. Additionally our algorithm, the Grammar Transform Analysis and Compression (GTAC) entropy estimator, uses a novel data structure to repeatedly solve the longest non-overlapping pattern problem in linear time. GTAC beats all known competitors in running time, in the low values of its entropy estimates, and in the properties that have been proven about it. 1 Introduction With the complete DNA sequences of many organisms already known, and the goal of completely sequencing the human genome making steady progress, the challenge of using this wealth of genetic information beneficially presents a new series of problems to be solved. One such problem is recognizing and characterizing the different regions of DNA and their different functions. Information theoretic entropy is one tool that can be used to help solve these types of problems.
The Incompressibility Method.
. We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are: (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency (how far it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.  Key words. Kolmogorov complexity, incompressiblity method, random graphs, enumeration of graphs, algorithmic information theory  AMS subject classifications. 68Q30, 05C80, 05C35, 05C30  1. Introduction. The incompressibility of individual random objects yields a simple but powerful proof technique. The incompressibility method, [9], is a new general purpose tool and should be compared with the pigeon hole principle or the probabilistic method. Here we apply the incompressibility metho...
Near optimal multiple alignment within a band in polynomial time.
Multiple sequence alignment is one of the most important problems in computational biology. Because of its notorious difficulties, aligning sequences within a constant band is a popular practice in bioinformatics with good results [17; 13; 14; 15; 1; 3; 6; 20; 18]. However, the problem is still NP-hard for multiple sequences. In this paper, we present polynomial time approximation schemes (PTAS) for multiple sequence alignment within a constant band, under standard models of SP alignment and consensus (star) alignment. The algorithms work for very general score schemes. In order to prove our main results, we also present a PTAS for SP alignment and a PTAS for consensus alignment, allowing only constant number of insertion and deletion gaps (of arbitrary length) per sequence on the average.  1. 
A Whole Correlation Structure of Asymptotically Self%2DSimilar Traffic in Communication Networks.
A closed form of autocorrelation functions about asymptotically self-similar processes is presented. The verification shows that this form best the real-trajfic data on Ethernet investigated satisfactorily. Ke;ywords: teletraffic modeling, long-range dependence, autocorrelation fimctions 1.
Applying MDL to learn best model granularity.
The Minimum Description Length (MDL) principle is solidly based on a  provably ideal method of inference using Kolmogorov complexity. We test how  the theory behaves in practice on a general problem in model selection: that  of learning the best model granularity. The performance of a model depends  critically on the granularity, for example the choice of precision of the parameters.  Too high precision generally involves modeling of accidental noise and  too low precision may lead to confusion of models that should be distinguished.  This precision is often determined ad hoc. In MDL the best model is the one  that most compresses a two-part code of the data set: this embodies &#034;Occam&#039;s  Razor.&#034; In two quite different experimental settings the theoretical value determined  using MDL coincides with the best value found experimentally. In  the first experiment the task is to recognize isolated handwritten characters in  one subject&#039;s handwriting, irrespective of size and orientation. Base...
On The Closest String and Substring Problems
The problem of finding a center string that is `close&#039; to every given string arises in computational molecular biology and coding theory. This problem has two versions: the Closest String problem and the Closest Substring problem. Given a set of strings  S = fs 1 ; s 2 ; : : : ; s n g, each of length m, the Closest String problem is to find the smallest  d and a string s of length m which is within Hamming distance d to each s i 2 S. This problem comes from coding theory when we are looking for a code not too far away from a given set of codes. Closest Substring problem, with an additional input integer L, asks for the smallest d and a string s, of length L, which is within Hamming distance d away from a substring, of length L, of each s i . This problem is much more elusive than the Closest String problem. The Closest Substring problem is formulated from applications in finding conserved regions, identifying genetic drug targets and generating genetic probes in molecular biology. Whether there are efficient approximation algorithms for both problems are major open questions in this area. We present two polynomial time approximation algorithms with approximation ratio 1 + ffl for any small ffl to settle both questions.
Applying MDL to Learning Best Model Granularity
The Minimum Description Length (MDL) principle is solidly based on a  provably ideal method of inference using Kolmogorov complexity. We test how  the theory behaves in practice on a general problem in model selection: that  of learning the best model granularity. The performance of a model depends  critically on the granularity, for example the choice of precision of the parameters.  Too high precision generally involves modeling of accidental noise and  too low precision may lead to confusion of models that should be distinguished.  This precision is often determined ad hoc. In MDL the best model is the one  that most compresses a two-part code of the data set: this embodies &#034;Occam&#039;s  Razor.&#034; In two quite different experimental settings the theoretical value determined  using MDL coincides with the best value found experimentally. In  the first experiment the task is to recognize isolated handwritten characters in  one subject&#039;s handwriting, irrespective of size and orientation. Base...
Fixed topology alignment with recombination.
In this paper, we study a new version of multiple sequence alignment, fixed topology  alignment with recombination. We show that it can not be approximated within any  constant ratio unless P = NP . For a more restricted version, we show that the problem  is MAX-SNP-hard. This implies that there is no PTAS for this version unless P = NP .  We also propose approximation algorithms for a special case, where each internal node  has at most one recombination child and any two merge paths for different recombination  nodes do not share any common node.  Key words: approximation algorithm, computational biology, evolutionary tree, multiple sequence alignment, phylogeny, recombination.  1 Introduction  Multiple sequence alignment is the most critical cutting-edge tool for extracting and representing biologically important commonalities from a set of sequences. It plays an essential role in the solution of many problems such as searching for highly conserved subregions among a set of biologica...
Minimum description length induction%2C Bayesianism%2C and Kolmogorov complexity.
The relationship between the Bayesian approach and the minimum description length approach is established. We sharpen and clarify the general modeling principles MDL and MML, abstracted as the ideal MDL principle and defined from Bayes&#039;s rule by means of Kolmogorov complexity. The basic condition under which the ideal principle should be applied is encapsulated as the Fundamental Inequality, which in broad terms states that the principle is valid when the data are random, relative to every contemplated hypothesis and also these hypotheses are random relative to the (universal) prior. Basically, the ideal principle states that the prior probability associated with the hypothesis should be given by the algorithmic universal probability, and the sum of the log universal probability of the model plus the log of the probability of the data given the model should be minimized. If we restrict the model class to the finite sets then application of the ideal principle turns into Kolmogorov&#039;s mi...
A lower bound on the average%2Dcase complexity of shellsort.
We give a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a p-pass Shellsort for any incremental sequence is \Omega\Gamma pn  1+1=p  ) for every p. The proof is an example of the use of Kolmogorov complexity (the incompressibility method) in the analysis of algorithms. 1 Introduction  The question of a nontrivial general lower bound (or upper bound) on the average complexity of Shellsort (due to D.L. Shell [14]) has been open for about four decades [5, 13]. We present such a lower bound for  p-pass Shellsort for every p.  Shellsort sorts a list of n elements in p passes using a sequence of increments h 1 ; : : : ; h p . In the kth  pass the main list is divided in h k separate sublists of length dn=h k e, where the ith sublist consists of the elements at positions j, where j mod h k = i \Gamma 1, of the main list (i = 1; : : : ; h k ). Every sublist is sorted using a straightforward insertion sort. The effi...
Some Open Problems in Computational Molecular Biology.

Average%2DCase Analysis of Algorithms Using Kolmogorov Complexity.
Analyzing the average-case complexity of algorithms is a very practical but very  difficult problem in computer science. In the past few years, we have demonstrated that  Kolmogorov complexity is an important tool for analyzing the average-case complexity  of algorithms. We have developed the incompressibility method [7]. In this paper, we  use several simple examples to further demonstrate the power and simplicity of such  method. We prove bounds on the average-case number of stacks (queues) required for  sorting sequential or parallel Queueusort or Stacksort.
From Gene Trees to Species Trees.
This paper studies various algorithmic issues in reconstructing a species tree from gene trees under the duplication and the mutation cost model. This is a fundamental problem in computational molecular biology. Our main results are as follows. 1. A linear time algorithm is presented for computing all the losses in duplications associated with the least common ancestor mapping from a gene tree to a species tree. This answers a problem raised recently by Eulenstein et al. (1998). 2. The complexity of finding an optimal species tree from gene trees is studied. The problem is proved to be NP-hard for the duplication cost and for the mutation cost. Further, the concept of reconciled trees was introduced by Goodman et al. and formalized by Page for visualizing the relationship between gene and species trees. We show that constructing an optimal reconciled tree for gene trees is also NP-hard. Finally, we consider a general reconstruction problem and show it to be NP-hard even for the well-kn...
A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application.
. Inferring evolutionary trees has long been a challenging problem both for biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quartet topologies) and then recombining these inferred quartet topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomial time algorithms with performance guarantees for quartet methods. To achieve this result the natural denseness of the set Q is exploited. The second result is a new technique, called quartet cleaning, that detects and corrects errors in the set Q with performance guarantees. This result h...
New applications of the incompressibility method Part II.
The incompressibility method is an elementary yet powerful proof technique based  on Kolmogorov complexity. It has been used successfully in many areas [8]. To further  demonstrate its power and elegance we exhibit new simple proofs using the incompressibility  method.  1 Introduction  The incompressibility of individual random objects yields a simple but powerful proof technique:  the incompressibility method. This method is a general purpose tool that can be used to prove lower bounds on computational problems, to obtain combinatorial properties of concrete objects, and to analyze the average complexity of an algorithm. Since the early 1980&#039;s, the incompressibility method has been successfully used to solve many well-known questions that had been open for a long time and to supply new simplified proofs for known results. A survey is [8].  The purpose of this paper is pragmatic, in the same style as [9, 7]. We want to further demonstrate how easy the incompressibility method can be us...
Quartet Cleaning Improved Algorithms and Simulations.
A critical step in all quartet methods for constructing evolutionary trees is the inference of the topology for each set of four species (i.e. quartet). It is a well-known fact that all quartet topology inference methods make mistakes that result in the incorrect inference of quartet topology. These mistakes are called quartet errors. In this paper, two efficient algorithms for correcting bounded numbers of quartet errors are presented. These &#034;quartet cleaning&#034; algorithms are shown to be optimal in that no algorithm can correct more quartet errors. An extensive simulation study reveals that sets of quartet topologies inferred by three popular methods (Neighbor Joining [15], Ordinal Quartet [14] and Maximum Parsimony [10]) almost always contain quartet errors and that a large portion of these quartet errors are corrected by the quartet cleaning algorithms.
New Applications of the Incompressibility Method.
The incompressibility method is an elementary yet powerful proof technique based  on Kolmogorov complexity. It has been used successfully in many areas [8]. To further  demonstrate its power and elegance we exhibit new simple proofs using the incompressibility  method.  1 Introduction  The incompressibility of individual random objects yields a simple but powerful proof technique:  the incompressibility method. This method is a general purpose tool that can be used to prove lower bounds on computational problems, to obtain combinatorial properties of concrete objects, and to analyze the average complexity of an algorithm. Since the early 1980&#039;s, the incompressibility method has been successfully used to solve many well-known questions that had been open for a long time and to supply new simplified proofs for known results. A survey is [8].  The purpose of this paper is pragmatic, in the same style as [9, 7]. We want to further demonstrate how easy the incompressibility method can be us...
Average%2DCase Complexity of Shellsort.
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a p-pass Shellsort for any incremental sequence is \Omega\Gamma pn  1+  1  p  ) for all p  log n. Using similar arguments, we analyze the average-case complexity of several other sorting algorithms. 1 Introduction  The question of a nontrivial general lower bound (or upper bound) on the average complexity of Shellsort (due to D.L. Shell [15]) has been open for about four decades [7, 14]. We present such a lower bound for p-pass Shellsort for every p.  Shellsort sorts a list of n elements in p passes using a sequence of increments h 1 ; : : : ; h p . In the kth pass the main list is divided in h k separate sublists of length n=h k , where the ith sublist consists of the elements at positions j, where j mod h k , of the main list (i = 1; : : : ; h k ). Every sublist is sorted using a straightforward insertion sort. The efficiency of the method is gove...
The Expected Size of Heilbronn%27s Triangles.
Heilbronn&#039;s triangle problem asks for the least \Delta such that n points lying in the unit disc necessarily contain a triangle of area at most \Delta. Heilbronn initially conjectured \Delta = O(1=n  2  ). As a result of concerted mathematical effort it is currently known that there are positive constants c and C such that  c log n=n  2   \Delta  C=n  8=7\Gammaffl  for every constant ffl ? 0. We resolve Heilbronn&#039;s problem in the expected case: If we uniformly at random put n points in the unit disc then the area of the smallest triangle has expectation \Theta(1=n  3  ) (and the smallest triangle has area \Theta(1=n  3  ) with probability almost one). Our proof uses the incompressibility method based on Kolmogorov complexity.   1 Introduction  An old problem by Heilbronn is as follows: Let  x 1 ; : : : ; xn be n points in the unit disc in the plane. Denote by A k (x 1 ; : : : ; xn ) the smallest area of all the polygons induced by the point sets fx i 1 ; : : : ; x i k g. Put  g k (n) =...
Some Examples of Average%2Dcase Analysis by the Imcompressibility Method.

SERF ODMG%2DBased Generic Re%2Dstructuring Facility.
The age of information management and with it the advent of increasingly sophisticated technologies have kindled a need in the database community and others to re-structure existing systems and move forward to make use of these new technologies. Legacy application systems are being transformed to newer state-of-the-art systems, information sources are being mapped from one data model to another, a diversity of data sources are being transformed to load, cleanse and consolidate data into modern data-warehouses [CR99]. Re-structuring is thus a critical task for a variety of applications. For this reason, most object-oriented database systems (OODB) today support some form of re-structuring support [Tec94, Obj93, BKKK87]. This existing support of current OODBs [BKKK87, Tec94, Obj93] is limited to a pre-de ned taxonomy of simple xed-semantic schema evolution operations. However, such simple changes, typically to individual types only, are not su cient for many advanced applications [Bre96]. More radical changes, such as combining two types or rede ning the relationship between two types, are either very di cult or even impossible to achieve with current commercial database technology [Tec94, Obj93]. In fact, most OODBs would typically require the user to write ad-hoc programs to accomplish This work was supported in part by the NSF NYI grant #IRI 94-57609. We would also like to thank our industrial sponsors, in particular, IBM for the IBM partnership award and Informix for software contribution. Special thanks also goes to the PSE Team
Recovering Branches on the Tree of Life An Approximation Algorithm.
Many fundamental questions in evolution remain unresolved despite the abundance of genetic sequence data that is now available to answer these questions. This state of affairs is largely due to the lack of efficient and accurate computational methods for inferring evolutionary trees. Efficient methods are critical since the abundance of sequence data has resulted in the desire to analyze large datasets. Methods with guaranteed accuracy are important since biologists require proof that results are meaningful. In this paper the first polynomial time approximation scheme (PTAS) for inferring evolutionary trees under the character compatibility paradigm is presented. PTAS&#039;s are highly desirable since they allow the approximation of an optimal solution with arbitrary precision in polynomial time. A requirement of this PTAS is that the data set, comprised of bipartitions of the species set, have size \Theta(n). This is shown to be a natural restriction and the Ordinal Split Method is present...
Distinguishing String Selection Problems.
This paper presents a collection of string algorithms that are at the core of several biological problems such as discovering potential drug targets, creating diagnostic probes, universal primers or unbiased consensus sequences. All these problems reduce to the task of finding a pattern that, with some error, occurs in one set of strings (Closest Substring Problem) and does not occur in another set (Farthest String Problem). In this paper, we break down the problem into several subproblems and prove the following results. 1. The following are all NP-Hard: the Farthest String Problem, the Closest Substring Problem, and the Closest String Problem of finding a string that is close to each string in a set. 2. There is a PTAS for the Farthest � String � Problem based on a linear programming relaxation technique. 43 3. There is a polynomial-time + ɛ-approximation algorithm for the Closest String Problem for any small constant ɛ&gt;0. Using this algorithm, we also provide an efficient heuristic algorithm for the Closest Substring Problem. 4. The problem of finding a string that is at least Hamming distance d from as many strings in a set as possible,
Finding Similar Regions in Many Strings.
Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems. We solve three main open questions in this area. Assume that we are given n DNA sequences  s1 ; : : : ; sn . The Consensus Patterns problem, which has been widely studied in bioinformatics research [26, 16, 12, 25, 4, 6, 15, 22, 24, 27], in its simplest form, asks for a region of length L in each s i , and a median string s of length L so that the total Hamming distance from s to these regions is minimized. We show the problem is NPhard and give a polynomial time approximation scheme (PTAS) for it. We also give a PTAS for the problem under the original measure of [26, 16, 12, 25]. As an interesting application of our analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important star alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence. The Closest String problem [2, 3, 7, 9, 18] asks for the smallest d and a string s which is within Hamming distance d to each s i . The problem is NP-hard [7, 18]. [3] gives a polynomial time algorithm for constant d. For super-logarithmic d, [2, 9] give efficient approximation algorithms using linear program ralaxation techniques. The best polynomial time approximation has ratio  4 3 for all d,  given by [18] ([9] also independently claimed the  4 3 ratio but only for super-logarithmic d). We settle the problem with a PTAS. We then give the first nontrivial better-than-2 approximation with ratio 2 \Gamma  2 2j\Sigmaj+1 for the more elusive Closest
Finding Similar Regions in Many Strings.
Algorithms for finding similar, or highly conserved, regions in a group of sequences are at the core of many molecular biology problems. We solve three main open questions in this area. Assume that we are given n DNA sequences  s1 ; : : : ; sn . The Consensus Patterns problem, which has been widely studied in bioinformatics research [26, 16, 12, 25, 4, 6, 15, 22, 24, 27], in its simplest form, asks for a region of length L in each s i , and a median string s of length L so that the total Hamming distance from s to these regions is minimized. We show the problem is NPhard and give a polynomial time approximation scheme (PTAS) for it. We also give a PTAS for the problem under the original measure of [26, 16, 12, 25]. As an interesting application of our analysis, we further obtain a PTAS for a restricted (but still NP-hard) version of the important star alignment problem allowing at most constant number of gaps, each of arbitrary length, in each sequence. The Closest String problem [2, 3, 7, 9, 18] asks for the smallest d and a string s which is within Hamming distance d to each s i . The problem is NP-hard [7, 18]. [3] gives a polynomial time algorithm for constant d. For super-logarithmic d, [2, 9] give efficient approximation algorithms using linear program ralaxation techniques. The best polynomial time approximation has ratio  4 3 for all d,  given by [18] ([9] also independently claimed the  4 3 ratio but only for super-logarithmic d). We settle the problem with a PTAS. We then give the first nontrivial better-than-2 approximation with ratio 2 \Gamma  2 2j\Sigmaj+1 for the more elusive Closest
On the Linear%2DCost Subtree%2DTransfer Distance between Phylogenetic Trees.
Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria [14] or from different genes [10] in the study of molecular evolution. Comparing these trees to find their similarities and dissimilarities (i.e.  distance) is thus an important issue in computational molecular biology. Several distance metrics including the nearest neighbor interchange (nni) distance and the subtree-transfer  distance have been proposed and extensively studied in the literature. This article considers a natural extension of the subtree-transfer distance, called the linear-cost subtree-transfer distance, and studies the complexi ty and efficient approximation algorithms for this distance as well as its relation ship to the nni distance. The linear-cost subtree-transfer model seems more logical t han the (unit-cost) subtree-transfer model in some applications. The following is a list of our results. 1. The linear-cost subtree-transfer d...
Average%2DCase Complexity of Shellsort %28Preliminary version%29

Average%2DCase Complexity of Shellsort
We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a p-pass Shellsort for any incremental sequence is \Omega\Gamma pn  1+  1  p  ) for all p  log n. Using similar arguments, we analyze the average-case complexity of several other sorting algorithms. 1 Introduction  The question of a nontrivial general lower bound (or upper bound) on the average complexity of Shellsort (due to D.L. Shell [15]) has been open for about four decades [7, 14]. We present such a lower bound for p-pass Shellsort for every p.  Shellsort sorts a list of n elements in p passes using a sequence of increments h 1 ; : : : ; h p . In the kth pass the main list is divided in h k separate sublists of length n=h k , where the ith sublist consists of the elements at positions j, where j mod h k , of the main list (i = 1; : : : ; h k ). Every sublist is sorted using a straightforward insertion sort. The efficiency of the method is gove...
Minimum Description Length Induction%2C Bayesianism%2C and Kolmogorov Complexity
The relationship between the Bayesian approach and the minimum description length approach is established. We sharpen and clarify the general modeling principles MDL and MML, abstracted as the ideal MDL principle and defined from Bayes&#039;s rule by means of Kolmogorov complexity. The basic condition under which the ideal principle should be applied is encapsulated as the Fundamental Inequality, which in broad terms states that the principle is valid when the data are random, relative to every contemplated hypothesis and also these hypotheses are random relative to the (universal) prior. Basically, the ideal principle states that the prior probability associated with the hypothesis should be given by the algorithmic universal probability, and the sum of the log universal probability of the model plus the log of the probability of the data given the model should be minimized. If we restrict the model class to the finite sets then application of the ideal principle turns into Kolmogorov&#039;s mi...
The Average%2DCase Area of Heilbronn%2DType Triangles
 From among �  � n triangles with vertices chosen from n points in the unit square, 3 let T be the one with the smallest area, and let A be the area of T. Heilbronn’s triangle problem asks for the maximum value assumed by A over all choices of n points. We consider the average-case: If the n points are chosen independently and at random (with a uniform distribution), then there exist positive constants c and C such that c/n3 &lt;µ n &lt; C/n3 for all large enough values of n, where µ n is the expectation of A. Moreover, c/n3 &lt;A&lt;C/n3, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in
New Applications of the Incompressibility Method.
The incompressibility method is an elementary yet powerful proof technique based  on Kolmogorov complexity. It has been used successfully in many areas [8]. To further  demonstrate its power and elegance we exhibit new simple proofs using the incompressibility  method.  1 Introduction  The incompressibility of individual random objects yields a simple but powerful proof technique:  the incompressibility method. This method is a general purpose tool that can be used to prove lower bounds on computational problems, to obtain combinatorial properties of concrete objects, and to analyze the average complexity of an algorithm. Since the early 1980&#039;s, the incompressibility method has been successfully used to solve many well-known questions that had been open for a long time and to supply new simplified proofs for known results. A survey is [8].  The purpose of this paper is pragmatic, in the same style as [9, 7]. We want to further demonstrate how easy the incompressibility method can be us...
Twist%2DRotation Transformations of Binary Trees and Arithmetic Expressions.

Approximation Algorithms for Directed Steiner Problems.
We give the first non-trivial approximation algorithms for the Steiner tree problem and  the generalized Steiner network problem on general directed graphs. These problems have  several applications in network design and multicast routing. For both problems, the best  ratios known before our work were the trivial O(k)-approximations. For the directed Steiner  tree problem, we design a family of algorithms that achieves an approximation ratio of  i(i \Gamma 1)k  1=i  in time O(n  i  k  2i  ) for any fixed i ? 1, where k is the number of terminals. Thus,  an O(k  ffl  ) approximation ratio can be achieved in polynomial time for any fixed ffl ? 0.  Setting i = log k, we obtain an O(log  2  k) approximation ratio in quasi-polynomial time. For  the directed generalized Steiner network problem, we give an algorithm that achieves an  approximation ratio of O(k  2=3  log  1=3  k), where k is the number of pairs of vertices that are  to be connected. Related problems including the group Steiner...
Supervised and unsupervised fuzzy%2Dadaptive Hamming net.

Kolmogorov Random Graphs and the Incompressibility Method.
. We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are: (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency (how far it falls short of the maximum possible Kolmogorov complexity) and (ii) a new elementary proof for the number of unlabeled graphs.  Key words. Kolmogorov complexity, incompressiblity method, random graphs, enumeration of graphs, algorithmic information theory  AMS subject classifications. 68Q30, 05C80, 05C35, 05C30  1. Introduction. The incompressibility of individual random objects yields a simple but powerful proof technique. The incompressibility method, [9], is a new general purpose tool and should be compared with the pigeon hole principle or the probabilistic method. Here we apply the incompressibility metho...
Some open problems in computational molecular biology.

Average%2DCase Analysis Using Kolgomorov Complexity %28Abstract%29.

Better Approximation of Diagonal%2DFlip Transformation and Rotation Transformation.

Fixed Topology Alignment with Recombination.
In this paper, we study a new version of multiple sequence alignment, fixed topology  alignment with recombination. We show that it can not be approximated within any  constant ratio unless P = NP . For a more restricted version, we show that the problem  is MAX-SNP-hard. This implies that there is no PTAS for this version unless P = NP .  We also propose approximation algorithms for a special case, where each internal node  has at most one recombination child and any two merge paths for different recombination  nodes do not share any common node.  Key words: approximation algorithm, computational biology, evolutionary tree, multiple sequence alignment, phylogeny, recombination.  1 Introduction  Multiple sequence alignment is the most critical cutting-edge tool for extracting and representing biologically important commonalities from a set of sequences. It plays an essential role in the solution of many problems such as searching for highly conserved subregions among a set of biologica...
Orchestrating Quartets Approximation and Data Correction.
Inferring evolutionary trees has long been a challenging problem both for biologists and computer scientists. In recent years research has concentrated on the quartet method paradigm for inferring evolutionary trees. Quartet methods proceed by first inferring the evolutionary history for every set of four species (resulting in a set Q of inferred quartet topologies) and then recombining these inferred quartet topologies to form an evolutionary tree. This paper presents two results on the quartet method paradigm. The first is a polynomial time approximation scheme (PTAS) for recombining the inferred quartet topologies optimally. This is an important result since, to date, there have been no polynomialtime algorithms with performance guarantees for quartet methods. In fact, this is the first known PTAS for inferring evolutionary trees under any paradigm. To achieve this result the natural denseness of the set Q is exploited. The second...
On reconstructing species trees from gene trees in term of duplications and losses.
This paper studies various properties of the least common ancestors mapping, the duplication and mutation costs, and the complexity of finding a species tree from gene trees.  1 Introduction  Since DNA sequences have become easier to obtain, emphasis has been placed on constructing gene trees and from these, reconstructing evolutionary trees for species (called species trees) in the evolutionary biology([8, 18, 6]). The current strategy for reconstructing species trees is based on the separate consideration of distinct gene families represented by homologous sequences. The homologous sequences are assumed to evolve in the same way as species. However, because of the presence of paralogy, sorting of ancestral polymorphism and horizontal transfer, gene trees and species trees are often inconsistent([19, 23, 26, 28]). Hence, a major problem that arises is how to reconcile different, sometimes contradictory, gene trees into a species tree([7]). This problem has been studied extensively for...
Approximation Algorithms for Directed Steiner Problems.
We give the first non-trivial approximation algorithms for the Steiner tree problem and  the generalized Steiner network problem on general directed graphs. These problems have  several applications in network design and multicast routing. For both problems, the best  ratios known before our work were the trivial O(k)-approximations. For the directed Steiner  tree problem, we design a family of algorithms that achieves an approximation ratio of  i(i \Gamma 1)k  1=i  in time O(n  i  k  2i  ) for any fixed i ? 1, where k is the number of terminals. Thus,  an O(k  ffl  ) approximation ratio can be achieved in polynomial time for any fixed ffl ? 0.  Setting i = log k, we obtain an O(log  2  k) approximation ratio in quasi-polynomial time. For  the directed generalized Steiner network problem, we give an algorithm that achieves an  approximation ratio of O(k  2=3  log  1=3  k), where k is the number of pairs of vertices that are  to be connected. Related problems including the group Steiner...
New Applications of the Incompressibility Method Part II
The incompressibility method is an elementary yet powerful proof technique based  on Kolmogorov complexity. It has been used successfully in many areas [8]. To further  demonstrate its power and elegance we exhibit new simple proofs using the incompressibility  method.  1 Introduction  The incompressibility of individual random objects yields a simple but powerful proof technique:  the incompressibility method. This method is a general purpose tool that can be used to prove lower bounds on computational problems, to obtain combinatorial properties of concrete objects, and to analyze the average complexity of an algorithm. Since the early 1980&#039;s, the incompressibility method has been successfully used to solve many well-known questions that had been open for a long time and to supply new simplified proofs for known results. A survey is [8].  The purpose of this paper is pragmatic, in the same style as [9, 7]. We want to further demonstrate how easy the incompressibility method can be us...
New Applications of the Incompressibility Method Part I
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas [10]. To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method. 1 Introduction  The incompressibility of individual random objects yields a simple but powerful proof technique:  the incompressibility method. This method is a general purpose tool that can be used to prove lower bounds on computational problems, to obtain combinatorial properties of concrete objects, and to analyze the average complexity of an algorithm. Since the early 1980&#039;s, the incompressibility method has been successfully used to solve many well-known questions that had been open for a long time and to supply new simplified proofs for known results. A survey is [10]. The purpose of this paper is pragmatic, in the same style as [11]. We want to further demonstrate how easy the incompressibility method can be used, via a new collection of simple e...
On the Complexity and Approximation of Syntenic Distance.
The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau and Sankoff. Here, a chromosome is represented as a set of genes and a genome is a collections of chromosomes. The syntenic distance between two genomes is defined as the minimum number of translocations, fusions and fissions required to transform one genome into the other. We prove that computing the syntenic distance is NP-hard and give a simple approximation algorithm with performance ratio 2. For the case when an upper bound d on the syntenic distance is known, we show that an an optimal syntenic sequence can be found in  O(nk + 2  O(d  2  )  ) time, where n and k are the number of chromosomes in the two given genomes. Next, we show that if the set of operations for transforming a genome is significantly restricted, we can nevertheless find a solution that performs at most O(logd) additional moves, wher...
Information Distance.
While Kolmogorov complexity is the accepted absolute measure of information  content in an individual finite object, a similarly absolute notion  is needed for the information distance between two individual objects, for  example, two pictures. We give several natural definitions of a universal  information metric, based on length of shortest programs for either ordinary  computations or reversible (dissipationless) computations. It turns  out that these definitions are equivalent up to an additive logarithmic  term. We show that the information distance is a universal cognitive similarity  distance. We investigate the maximal correlation of the shortest  programs involved, the maximal uncorrelation of programs (a generalization  of the Slepian-Wolf theorem of classical information theory), and the  density properties of the discrete metric spaces induced by the information  distances. A related distance measures the amount of nonreversibility of  a computation. Using the physical theo...
Addition in log2n   O%281%29 Steps on Average A Simple Analysis.

Algorithmic Learning Theory
We shall present the construction and analysis of a universal estimator for the mathematical problem of supervised learning. In this problem, we observe the data z = (z1,..., zm)  ⊂ X × Y of m independent random observations zi = (xi, yi), i = 1,..., m, identically distributed according to a probability ρ on a product space X × Y. We are interested in estimating the regression function fρ(x) defined as the conditional expectation of the random variable y at x: fρ(x): = ydρ(y|x) Y with ρ(y|x) the conditional probability measure with respect to x. The estimator fz is assessed by the measure of the error ‖fρ − fz ‖ in the L 2 (X, ρX) metric with ρX the marginal probability which is unknown. This type of problem is refered to as distribution-free, see [?] for a general introduction. Universal means that the estimator does not depend on any a priori assumptions about the regression function to be estimated. Our universal estimator, introduced in [?], consists of a least-square fitting procedure using piecewise constant
Average%2DCase Analysis Using Kolmogorov Complexity.

On Prediction by Data Compression.
. Traditional wisdom has it that the better a theory compresses the learning data concerning some phenomenon under investigation, the better we learn, generalize, and the better the theory predicts unknown data. This belief is vindicated in practice but apparently has not been rigorously proved in a general setting. Making these ideas rigorous involves the length of the shortest effective description of an individual object: its Kolmogorov complexity. In a previous paper we have shown that optimal compression is almost always a best strategy in hypotheses identification (an ideal form of the minimum description length (MDL) principle). Whereas the single best hypothesis does not necessarily give the best prediction, we demonstrate that nonetheless compression is almost always the best strategy in prediction methods in the style of R. Solomonoff. 1 Introduction  Given a body of data concerning some phenomenon under investigation, we want to select the most plausible hypothesis from amon...
Average%2DCase Analysis via Incompressibility.

On the complexity and approximation of syntenic distance.
The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau and Sankoff. Here, a chromosome is represented as a set of genes and a genome is a collections of chromosomes. The syntenic distance between two genomes is defined as the minimum number of translocations, fusions and fissions required to transform one genome into the other. We prove that computing the syntenic distance is NP-hard and give a simple approximation algorithm with performance ratio 2. For the case when an upper bound d on the syntenic distance is known, we show that an an optimal syntenic sequence can be found in  O(nk + 2  O(d  2  )  ) time, where n and k are the number of chromosomes in the two given genomes. Next, we show that if the set of operations for transforming a genome is significantly restricted, we can nevertheless find a solution that performs at most O(logd) additional moves, wher...
On Distances between Phylogenetic Trees %28Extended Abstract%29.

Formal Models and Computability.
Efforts to build &amp;quot;secure &amp;quot; computer systems have now been underway for more than a decade. Many designs have been proposed, some prototypes have been constructed, and a few systems are approaching the production stage. A small number of systems are even operating in what the Department of Defense calls the &amp;quot;multilevel &amp;quot; mode some
Reversible Simulation of Irreversible Computation by Pebble Games

Reversibility and Adiabatic Computation Trading Time and Space for Energy
Future miniaturization and mobilization of computing devices requires energy parsimonious `adiabatic&#039; computation. This is contingent on logical reversibility of computation. An example is the idea of quantum computations which are reversible except for the irreversible observation steps. We propose to study quantitatively the exchange of computational resources like time and space for irreversibility in computations. Reversible simulations of irreversible computations are memory intensive. Such (polynomial time) simulations are analysed here in terms of `reversible&#039; pebble games. We show that Bennett&#039;s pebbling strategy uses least additional space for the greatest number of simulated steps. We derive a trade-off for storage space versus irreversible erasure. Next we consider reversible computation itself. An alternative proof is provided for the precise expression of the ultimate irreversibility cost of an otherwise reversible computation without restrictions on time and space use. A ...
Pyramid edge detection based on stack filter.
We introduce palmprint verification, one of the most reliable personal identification methods in the biometric technology. In this paper, a new approach to the palmprint verification based on nearest neighbor vector (NNV) is presented. Initially we find the datum point of palmprint, which have a remarkable advantage about their spatial location. We find all possible line pairs using NNV, followed by a first level preliminary match using the nearest neighbor lines, and then a second level match is carried out by considering the global datum point feature of palmprints to overcome the possible distortion. The two level analyses based on the NNV and datum point helps in effective palmprint verification. With several palmprint images, we tested out proposed verification system and the experimental results shows that the performance of our algorithm is good.
Foreword %28COCOON%2795%29.

Inferring a DNA Sequence from Erroneous Copies.

Some Notes on the Nearest Neighbour Interchange Distance.
. We present some new results on a well known distance measure between evolutionary trees. The trees we consider are free 3-trees having n leaves labeled 0; : : : ; n \Gamma 1 (representing species), and n \Gamma 2 internal nodes of degree 3. The distance between two trees is the minimum number of nearest neighbour interchange (NNI) operations required to transform one into the other. First, we improve an upper bound on the nni-distance between two arbitrary n-node trees from 4n log n [2] to  n log n. Second, we present a counterexample disproving several theorems in [13]. Roughly speaking, finding an equal partition between two trees doesn&#039;t imply decomposability of the distance finding problem. Third, we present a polynomial-time approximation algorithm that, given two trees, finds a transformation between them of length O(log n) times their distance. We also present some results of computations we performed on small size trees. 1 Introduction  In a free 3-tree, n leaf nodes, labeled...
Reversible Simulation of Irreversible Computation.
This paper takes up this suggestion to analyze time-space and space-irreversibility tradeoffs. It completely characterizes the realizable pebble configurations of the reversible pebble games (they encode the reachable instantaneous descriptions of a Turing machine reversibly simulating an irreversible computation). As corollary we obtain Bennett&#039;s earlier [3] simulaing Group Nr. 8556, and by NWO through NFI Project ALADDIN under Contract number NF 62-376 and NSERC under International Scientific Exchange Award ISE0125663. Affiliations are CWI and the University of Amsterdam.  tion and a first proof that this simulation is a space-optimal pebble game. It also introduces irreversible steps and gives a theorem on the tradeoff between the number of allowed irreversible steps and the memory gain in the pebble game. For such a tradeoff the limited irreversible actions have to take place at precise times during the reversible simulation, and cannot be delayed to be executed all together at the end of the computation (as is possible in computations without time or space resource bounds). Finally, in all such reversible simulations it is assumed that the number of steps to be simulated is known in advance and used to construct the simulation (for that number of steps). We show how to reversibly simulate an irreversible computation of unknown computing time, using the same order of magnitude of simulation time. 1.1 Reversible Turing Machines In the standard model of a Turing machine the elementary operations are rules in quadruple format (p; s; a; q) meaning that if the finite control is in state p
Addition in log2n   O%281%29 Steps on Average A Simple Analysis

Lower Bounds on Learning Decision Lists and Trees.

How to Share Concurrent Wait%2DFree Variables.
Sharing data between multiple asynchronous users---each of which can atomically read and write the data---is a feature which may help to increase the amount of parallelism in distributed systems. An algorithm implementing this feature is presented. The main construction of an n-user  atomic variable directly from single-writer, single-reader atomic variables uses O(n) control bits and O(n) accesses per Read/Write running in O(1)  parallel time.  1980 Mathematics Subject Classification: 68C05, 68C25, 68A05, 68B20.  CR Categories: B.3.2, B.4.3, D.4.1, D.4.4.  Keywords and Phrases: Shared variable (register), concurrent reading and writing, atomicity, multiwriter.   M. Li was supported in part by the National Science Foundation under Grant DCR8606366 at Ohio State University, by Office of Naval Research Grant N00014-85-K-0445 and Army Research Office Grant DAAL03-86-K-0171 at Harvard University, and by NSERC Grant OGP-0036747 at York University. E-mail adresses: mli@math.uwaterloo.ca, tro...
K One%2DWay Heads Cannot Do String%2DMatching.

DNA Sequencing and String Learning.
 In laboratories, the majority of large-scale DNA sequencing is done following the shot-gun strategy, which is to randomly sequence large amount of relatively short fragments and then heuristically find a shortest common superstring of the fragments [26]. We study mathematical frameworks, under plausible assumptions, suitable for massive automated DNA sequencing and for analyzing DNA sequencing algorithms. We model the DNA sequencing problem as learning a string from its randomly drawn substrings. Under certain restrictions, this may be viewed as string learning in Valiant&#039;s distribution-free learning model and in this case we give an efficient learning algorithm and a quantitative bound on how many examples suffice. One major obstacle to our approach turns out to be a quite well-known open question on how to approximate a shortest common superstring of a set of strings, raised by a number of authors in the last ten years [9, 29, 30]. We give the first provably good algorithm which approximates a shortest superstring of length n by a superstring of length O(n log n). The algorithm works equally well even in the presence of negative examples, i.e., when merging of some strings is prohibited.
Target indexing in SAR images using scattering centers and the Hausdorff distance.

Iterative Belief Revision in Extended Logic Programming.
Extended logic programming augments conventional logic programming with both default and explicit negation. Several semantics for extended logic programs have been proposed that extend the well-founded semantics for logic programs with default negation (called normal programs). We show that two of these extended semantics are intractable; both Dung&#039;s grounded argumentation semantics and the well-founded semantics of Alferes  et al. are NP-hard. Nevertheless, we also show that these two semantics have a common core, a more restricted form of the grounded semantics, which is tractable and can be computed iteratively in quadratic time. Moreover, this semantics is a representative of a rich class of tractable semantics based on a notion of iterative belief revision. 1 Introduction  The semantics of logic programs with two kinds of negation, default negation  and explicit negation, has been studied extensively in the recent literature (e.g. [1, 4, 9, 12, 16, 18, 19, 24, 25, 26, 27]). Logic ...
Computing and Combinatorics
. We give several examples where PVM was successfully  used as a tool for distributed computation of solutions of combinatorial  problems. Involved topics are the computation of the solution of multidimensional  subset sum problems which appear in the construction  of block designs, the construction and classification of finite solvable  groups up to isomorphism, and the computation of spin polynomials  that are generating functions of ribbon tableaux and which lead to  generalizations of Hall-Littlewood functions.  R&#039;esum&#039;e. Nous donnons plusieurs exemples pour lesquels nous avons  utilis&#039;e PVM comme outil de distribution de r&#039;esolution de probl`emes  combinatoires. Les sujets abord&#039;es sont la r&#039;esolution du probl`eme  du sac-`a-dos multi-dimensionnel qui apparait dans la construction  des &#034;block designs &#034;, la construction et la classification groupes finis  r&#039;esolubles `a isomorphismes pr`es, et le calcul des polynomes de spin qui  sont des fonctions g&#039;en&#039;eratrices de tableaux de rub...
Inferring a DNA Sequence from Erroneous Copies %28Abstract%29.

Lower Bounds on Learning Decision Lists and Trees %28Extended Abstract%29.

Algorithmic Arguments in Physics of Computation.
. We show the usefulness of incompressibility arguments based on Kolmogorov complexity in physics of computation by several examples. These include analysis of energy parsimonious `adiabatic&#039; computation, and scalability of network architectures. 1 Introduction  In [Shannon, 1948] C. Shannon formulated information theory dealing with the average number of bits required to communicate a message produced by a random source from a sender to a receiver who both agree on the ensemble of possible messages. In this theory, if the universe of messages consists of a two elements, a sentence &#034;let&#039;s go drink a beer&#034; and Homer&#039;s Illiad, both elements equally likely, then the Illiad can be transmitted by a single bit. This illustrates that, as Shannon points out, this theory does not say anything about the information content of individual objects, but only says something about the required information exchange for communication. In [Kolmogorov, 1965] A.N. Kolmogorov formulated a theory of informat...
Computational Machine Learning in Theory and Praxis.
In the last few decades a computational approach to machine learning has emerged based on paradigms from recursion theory and the theory of computation. Such ideas include learning in the limit, learning by enumeration, and probably approximately correct (pac) learning. These models usually are not suitable in practical situations. In contrast, statistics based inference methods have enjoyed a long and distinguished career. Currently, Bayesian reasoning in various forms, minimum message length (MML) and minimum description length (MDL), are widely applied approaches. They are the tools to use with particular machine learning praxis such as simulated annealing, genetic algorithms, genetic programming, artificial neural networks, and the like. These statistical inference methods select the hypothesis which minimizes the sum of the length of the description of the hypothesis (also called `model&#039;) and the length of the description of the data relative to the hypothesis. It appears to us th...
A New Approach to Formal Language Theory by Kolmogorov Complexity.
We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for regular languages, and a new method to separate deterministic context-free languages and nondeterministic context-free languages. The use of the new `incompressibility arguments&#039; is illustrated by many examples. The approach is also successful at the high end of the Chomsky hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov complexity. (This is a preliminary uncorrected version. The final version is the one published in SIAM J. Comput., 24:2(1995), 398-410.) 1 Introduction  It is feasible to reconstruct parts of formal language theory using algorithmic information theory (Kolmogorov complexity). We provide theorems on how to use Kolmogorov complexity as a concrete and powerful tool. We do not just want    A preliminary version of part of this work was presented at the 16th International...
On the Approximation of Shortest Common Supersequences and Longest Common Subsequences.

On the Approximation of Shortest Common Supersequences and Longest Common Subsequences.

Linear Approximation of Shortest Superstrings.
We consider the following problem: given a collection of strings s 1 ; . . . ; s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s. Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of distinct strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2n), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4n. Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3n. We also show the sup...
Learning Boolean Formulas.
In this paper we prove the intractability of learning several classes of Boolean functions in the distribution-free model (also called the Probably Approximately Correct or PAC model) of learning from examples. These results are representation independent, in that they hold regardless of the syntactic form in which the learner chooses to represent its hypotheses. Our methods reduce the problems of cracking a number of well-known public-key cryptosystems to the learning problems. We prove that a polynomial-time learning algorithm for Boolean formulae, deterministic finite automata or constant-depth threshold circuits would have dramatic consequences for cryptography and number theory: in particular, such an algorithm could be used to break the RSA cryptosystem, factor Blum integers (composite numbers equivalent to 3 modulo 4), and detect quadratic residues. The results hold even if the learning algorithm is only required to obtain a slight advantage in prediction over random guessing. T...
Kolmogorov Complexity Arguments in Combinatorics.
The utility of a Kolmogorov complexity method in combinatorial theory is demonstrated by several examples. 1 Introduction  Probabilistic arguments in combinatorial theory, as used by Erdos and Spencer [5], are usually aimed at establishing the existence of an object, in a nonconstructive sense. It is ascertained that a certain member of a class has a certain property, without actually exhibiting that object. Usually, the method proceeds by exhibiting a random process which produces the object with positive probability. Alternatively, a quantitative property is determined from a bound on its average in a probabilistic situation. The way to prove such `existential&#039; propositions often uses averages. We may call this    Supported by the NSERC operating grants OGP-0036747 and OGP-046506. Address: Computer Science Department, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1. Email: mli@math.waterloo.edu  y  Partially supported by the NSERC International Scientific Exchange Award ISE...
Three One%2DWay Heads Cannot Do String Matching.

Statistical Properties of Finite Sequences with High Kolmogorov Complexity.
We investigate to what extent finite binary sequences with high Kolmogorov complexity are normal (all blocks of equal length occur equally frequent), and the maximal length of all-zero or all-one runs which occur with certainty. 1 Introduction  Each individual infinite sequence generated by a (  1 2  ;  1 2 ) Bernoulli process (flipping a fair coin) has (with probability 1) the property that the relative frequency of zeros in an initial n-length segment goes to  1 2 for n goes to infinity. A related statement can be made for finite sequences, in the sense that one can say that the majority of all sequences will have about one half zeros.    Supported by the NSERC operating grant OGP-046506. Address: Computer Science Department, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1. Email: mli@math.uwaterloo.ca  y  Partially supported by the NSERC International Scientific Exchange Award ISE0046203 and by NWO through NFI Project ALADDIN under Contract number NF 62-376. Address: Centr...
Wait%2DFree Consensus Using Asynchronous Hardware.

Approximating Shortest Superstrings with Constraints.

Thermodynamics of computation and information distance.

k one%2Dway heads cannot do string%2Dmatching.

Approximating Shortest Superstrings with Constraints %28Extended Abstract%29.

Bonded Time%2DStamps.

Learning in the Presence of Malicious Errors.
In this paper we study an extension of the distribution-free model of learning introduced by Valiant [23] (also known as the probably approximately correct or PAC model) that allows the presence of malicious errors in the examples given to a learning algorithm. Such errors are generated by an adversary with unbounded computational power and access to the entire history of the learning algorithm&#039;s computation. Thus, we study a worst-case model of errors. Our results include general methods for bounding the rate of error tolerable by any learning algorithm, efficient algorithms tolerating nontrivial rates of malicious errors, and equivalences between problems of learning with errors and standard combinatorial optimization problems. 1 Introduction In this paper, we study a practical extension to Valiant&#039;s distribution-free model of learning: the presence of errors (possibly maliciously generated by an adversary) in the sample data. The distribution-free model typically makes the idealize...
On the Complexity of Learning Strings and Sequences.

Philosophical Issues in Kolmogorov Complexity.
this article at a conceptual level, it is sufficient to know that Kolmogorov complexity of a finite string x
Theory and Algorithms for Plan Merging.
Merging operators in a plan can yield significant savings in the cost to execute a plan. This paper provides a formal theory for plan merging and presents both optimal and efficient heuristic algorithms for finding minimum-cost merged plans. The optimal plan-merging algorithm applies a dynamic programming method to handle multiple linear plans and is extended to partially ordered plans in a novel way. Furthermore, with worst and average case complexity analysis and empirical tests, we demonstrate that efficient and well-behaved approximation algorithms are applicable for optimizing plans with large sizes.
Average Case Complexity Under the Universal Distribution Equals Worst%2DCase Complexity.
The average complexity of any algorithm whatsoever (provided it always terminates) under the  universal distribution is of the same order of magnitude as the worst-case complexity. This holds  both for time complexity and for space complexity. To focus our discussion, we use as illustrations  the particular case of sorting algorithms, and the general case of the average case complexity of NPcomplete  problems.  1 
Optimality of Wait%2DFree Atomic Multiwriter Variables.
Known implementations of concurrent wait-free atomic shared multiwriter variables use Q(n) control bits per subvariable. It has been shown that implementations of sequential time-stamp systems require W(n) control bits per subvariable. We exhibit a sequential wait-free atomic shared multiwriter variable construction using log n control bits per subvariable. There arises the question of the optimality of concurrent implementations of the same, and of weak time-stamp systems. We also show that our solutions are self-stabilizing. [Information Processing Letters, 43(1992), 107-112] 1980 Mathematics Subject Classification: 68C05, 68C25, 68A05, 68B20. CR Categories: B.3.2, B.4.3, D.4.1, D.4.4. Keywords and Phrases: Shared variable (register), concurrent reading and writing, atomicity, multiwriter variable, simulation. Note: this paper will be published elsewhere.  -- -- - 2 - 1. Introduction  In [La] it is shown how an atomic variable---one whose accesses appear to be indivisible---shared b...
A Note on Shortest Superstrings with Flipping.

Inductive Reasoning and Kolmogorov Complexity.

The Power of the Queue.
Queues, stacks, and tapes are basic concepts which have direct applications in compiler design and the general design of algorithms. Whereas stacks (pushdown store or last-in-first-out storage) have been thoroughly investigated and are well understood, this is much less the case for queues (first-infirst -out storage). In this paper we present a comprehensive study comparing queues to stacks and tapes (off-line and with one-way input). The techniques we use rely on Kolmogorov complexity. In particular, 1 queue and 1 tape (or stack) are not comparable: (1) Simulating 1 stack (and hence 1 tape) by 1 queue requires\Omega\Gamma  n  4=3  = log n)  time in both the deterministic and the nondeterministic cases. (2) Simulating 1 queue by 1 tape requires\Omega\Gamma  n  2  ) time in the deterministic case, and\Omega\Gamma  n  4=3  =(log n)  2=3  ) in the nondeterministic case; We further compare the relative power between different numbers of queues: (3) Nondeterministically simulating 2 queues...
A Quantitative Theory for Plan Merging.

On the Complexity of Learning Strings and Sequences.

Linear Approximation of Shortest Superstrings
We consider the following problem: given a collection of strings s 1 ; . . . ; s m , find the shortest string s such that each s i appears as a substring (a consecutive block) of s. Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of distinct strings with maximum overlap until only one string remains. Let n denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length O(n) (in fact, 2n), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent O(n log n) result. We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4n. Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3n. We also show the sup...
Combinatorics and Kolmogorov Complexity.
We investigate to what extent finite binary sequences with high Kolmogorov complexity are normal (all blocks of equal length occur equally frequent), and the maximal length of all-zero or all-one runs which occur with certainty. 1 Introduction  Each individual infinite sequence generated by a (  1 2  ;  1 2 ) Bernoulli process (flipping a fair coin) has (with probability 1) the property that the relative frequency of zeros in an initial n-length segment goes to  1 2 for n goes to infinity. A related statement can be made for finite sequences, in the sense that one can say that the majority of all sequences will have about one half zeros.    Supported by the NSERC operating grant OGP-046506. Address: Computer Science Department, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1. Email: mli@math.uwaterloo.ca  y  Partially supported by the NSERC International Scientific Exchange Award ISE0046203 and by NWO through NFI Project ALADDIN under Contract number NF 62-376. Address: Centr...

Resource Bounds for Parallel Computation of Threshold and Symmetric Functions.

Learning Simple Concept Under Simple Distributions.
  We aim at developing a learning theory where `simple&#039; concepts are easily learnable. In Valiant&#039;s learning model, many concepts turn out to be too hard (like NP hard) to learn. Relatively few concept classes were shown to be learnable polynomially. In daily life, it seems that things we care to learn are usually learnable. To model the intuitive notion of learning more closely, we do not require that the learning algorithm learns (polynomially) under all distributions, but only under all simple distributions. A distribution is simple if it is dominated by an enumerable distrib...
Towards a DNA Sequencing Theory %28Learning a String%29 %28Preliminary Version%29

Kolmogorov Complexity and its Applications.
This document has been prepared using the L a T E X system. We thank Donald Knuth for T E X, Leslie Lamport for L a T E X, and Jan van der Steen at CWI for online help. Some figures were prepared by John Tromp using the xpic program. The London Mathematical Society kindly gave permission to reproduce a long extract by A.M. Turing. The Indian Statistical Institute, through the editor of Sankhy¯a, kindly gave permission to quote A.N. Kolmogorov. We gratefully acknowledge the financial support by NSF Grant DCR8606366, ONR Grant N00014-85-k-0445, ARO Grant DAAL03-86-K0171, the Natural Sciences and Engineering Research Council of Canada through operating grants OGP-0036747, OGP-046506, and International Scientific Exchange Awards ISE0046203, ISE0125663, and NWO Grant NF 62-376. The book was conceived in late Spring 1986 in the Valley of the Moon in Sonoma County, California. The actual writing lasted on and off from autumn 1987 until summer 1993. One of us [PV] gives very special thanks to his lovely wife Pauline for insisting from the outset on the significance of this enterprise. The Aiken Computation Laboratory of Harvard University, Cambridge, Massachusetts, USA; the Computer Science Department of York University, Ontario, Canada; the Computer Science Department of the University  xii of Waterloo, Ontario, Canada; and CWI, Amsterdam, the Netherlands provided the working environments in which this book could be written. Preface to the Second Edition
A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution %28Extended Abstract%29

How to Share Concurrent Asynchronous Wait%2DFree Varaibles %28Preliminary Version%29.

A New Approach to Formal Language Theory by Kolmogorov Complexity %28Preliminary Version%29.

The Minimum Description Length Principle and Its Application to Online Learning of Handprinted Characters.

Inductive Reasoning and Komogorov Complexity.

Geometric Optimization and Dp %2D Completeness.


New lower bounds for parallel computation.
Abstract. Lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write PRAM with unlimited shared memory and unlimited power of individual processors (denoted by PRIORITY(m)): (1) It is proved that with a number of processors polynomial in n, fi(log n) time is needed for addition, multiplication or bitwise OR of n numbers, when each number has II ’ bits. Hence even the bit complexity (i.e., the time complexity as a function of the total number of bits in the input) is logarithmic in this case. This improves a beautiful result of Meyer auf der Heide and Wigderson [22]. They proved a log n lower bound using Ramsey-type techniques. Using Ramsey theory, it is possible to get an upper bound on the number of bits in the inputs used. However, for the case of polynomially many processors, this upper bound is more than a polynomial in n. (2) An R(log n) lower bound is given for PRIORITY(m) with no” ’ processors on a function with inputs from (0, 11, namely for the functionf(xl,.,x.)  = C:‘=, x,a ’ where a is fixed and x, E (0, 1). (3) Finally, by a new efficient simulation of PRIORITY(m) by unbounded fan-in circuits, that with less than exponential number of processors, it is proven a PRIORITY(m) cannot compute PARITY in constant time, and with nO” ’ processors Q(G) time is needed. The simulation technique is of
On the Learnability of Finite Automata.
This paper surveys some recent theoretical results on the efficiency of machine learning algorithms. The main tool described is the notion of Probably Approximately Correct (PAC) learning, introduced by Valiant. We define this learning model and then look at some of the results obtained in it. We then consider some criticisms of the PAC model and the extensions proposed to address these criticisms. Finally, we look briefly at other models recently proposed in computational learning theory.  2 Introduction  It&#039;s a dangerous thing to try to formalize an enterprise as complex and varied as machine learning so that it can be subjected to rigorous mathematical analysis. To be tractable, a formal model must be simple. Thus, inevitably, most people will feel that important aspects of the activity have been left out of the theory. Of course, they will be right. Therefore, it is not advisable to present a theory of machine learning as having reduced the entire field to its bare essentials. All ...
Learning in the Presence of Malicious Errors %28Extended Abstract%29

Tape versus Queue and Stacks The Lower Bounds

A Separator Theorem for One%2DDimensional Graphs Under Linear Mapping.

Simulating Two Pushdown Stores by One Tape in O%28n%5E1.5 sqrt%28log n%29%29 Time.

k 1 Heads Are Better than k for PDAs.

Bounded Time%2DStamps %28Extended Abstract%29

The Probabilistic and Deterministic Parallel Complexity of Symmetric Functions.

On Processor Coordination Using Asynchronous Hardware.
In Proceedings of the Seventh Annual ACM Symp. on Principles of Distributed Computing, 1988, pp. 28--37.  [35] R. Gallager. Finding a Leader in a Network with O(E + n log n) Messages, Internal memorandum, MIT. [36] R. Gallager, P. Humblet, and P. Spira. &#034;A Distributed Algorithm for Minimum-Weight Spanning Trees,&#034; ACM Transactions on Programming Languages and Systems, Vol. 5, No. 1 (January 1983), pp. 66--77. [37] M. Herlihy. &#034;Impossibility and Universality Results for Wait-Free Synchronization,&#034; In  Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing, pp. 276--290, August 1988. [38] D. Hirschberg and J. Sinclair. &#034;Decentralized Extrema-Finding in Circular Configurations of Processes,&#034; Communications of the ACM, Vol. 23 (November 1980), pp. 627-- 628. [39] L. Higham and T. Przytycka. &#034;A Simple, Efficient Algorit
On the Learnability of Boolean Formulae

Separation and Lower Bounds for ROM and Nondeterministic Models of Parallel Computation

k 1 Heads Are Better than k for PDA%27s

Containment%2C Separation%2C Complete Sets%2C and Immunity of Complexity Classes.

New Lower Bounds for Parallel Computation
Abstract. Lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write PRAM with unlimited shared memory and unlimited power of individual processors (denoted by PRIORITY(m)): (1) It is proved that with a number of processors polynomial in n, fi(log n) time is needed for addition, multiplication or bitwise OR of n numbers, when each number has II ’ bits. Hence even the bit complexity (i.e., the time complexity as a function of the total number of bits in the input) is logarithmic in this case. This improves a beautiful result of Meyer auf der Heide and Wigderson [22]. They proved a log n lower bound using Ramsey-type techniques. Using Ramsey theory, it is possible to get an upper bound on the number of bits in the inputs used. However, for the case of polynomially many processors, this upper bound is more than a polynomial in n. (2) An R(log n) lower bound is given for PRIORITY(m) with no” ’ processors on a function with inputs from (0, 11, namely for the functionf(xl,.,x.)  = C:‘=, x,a ’ where a is fixed and x, E (0, 1). (3) Finally, by a new efficient simulation of PRIORITY(m) by unbounded fan-in circuits, that with less than exponential number of processors, it is proven a PRIORITY(m) cannot compute PARITY in constant time, and with nO” ’ processors Q(G) time is needed. The simulation technique is of
The Power of the Queue.
Queues, stacks, and tapes are basic concepts which have direct applications in compiler design and the general design of algorithms. Whereas stacks (pushdown store or last-in-first-out storage) have been thoroughly investigated and are well understood, this is much less the case for queues (first-infirst -out storage). In this paper we present a comprehensive study comparing queues to stacks and tapes (off-line and with one-way input). The techniques we use rely on Kolmogorov complexity. In particular, 1 queue and 1 tape (or stack) are not comparable: (1) Simulating 1 stack (and hence 1 tape) by 1 queue requires\Omega\Gamma  n  4=3  = log n)  time in both the deterministic and the nondeterministic cases. (2) Simulating 1 queue by 1 tape requires\Omega\Gamma  n  2  ) time in the deterministic case, and\Omega\Gamma  n  4=3  =(log n)  2=3  ) in the nondeterministic case; We further compare the relative power between different numbers of queues: (3) Nondeterministically simulating 2 queues...
String%2DMatching Cannot be Done by a Two%2DHead One%2DWay Deterministic Finite Automation.

Simulating Two Pushdown Stores by One Tape in O%28n%5E1.5 sqrt%28log n%29%29 Time

Lower Bounds by Kolmogorov%2DComplexity %28Extended Abstract%29.

